C++ Dijkstraアルゴリズム - エッジ名/タイプを印刷

Question

現在、Dijkstraの最短経路問題に取り組んでいます。このプロジェクトでは何も具体的なものはありません。アルゴリズムは、頂点のタイプを別の頂点に印刷する必要があることを除いて、標準です（ペアのセットを実装しています）。

私は4つの頂点と5つのエッジがあるとします。 v1とv2を接続する2つ以上の辺が存在するように、1組の頂点p（v1、v2）が存在する。たとえば、ロンドンからパリまでの距離を求めたいとします。私たちはどちらも車で運転することができます（1つのタイプのエッジ）または私たちは航空券（別のタイプのエッジ）を購入することができます。私がしたいのは、エッジのタイプを印刷することです。

例： 私はロンドンからパリに行くには2通りの方法があります。 ロンドン - >カレー - >パリ、車で約5時間、 ロンドン - >パリ、飛行機で約1時間。

最小時間や最小距離の印刷方法、パスの印刷方法などはわかっていますが、「飛行機」や「車」などのエッジの種類（輸送の種類）を印刷するにはどうすればよいですか？ '？ここに私が試したものです：

struct neighbor { 

int target_vertex; 
double weight; 
int type; 
// for type: 0 - car 
// 1 - bus 
// 2 - plane 

}; 

しかし、それでもまだ、私は最短経路を計算しながら、私はそれらのエッジ「種類」を保存する方法を、見つけ出すことができませんでした。ここ

コード：https://gist.github.com/anonymous/5943c448e47ebf0d3964baa53361459d

Answer 1

可能性のあるすべてのシナリオをある都市から別の都市に事前定義して問題を解決しました（基本的にはすべての都市の組み合わせ）。

if (choice == 1) { 
    switch (from) { 
     case 0: { 
      if (to == 1) std::cout << " by foot "; 
      if (to == 2) std::cout << " by foot -> by bus "; 
      if (to == 3) std::cout << " by air "; 
      break; 
     } 
     case 1: { 
      if (to == 0) std::cout << " by foot "; 
      if (to == 2) std::cout << " by bus "; 
      if (to == 3) std::cout << " by bus -> by car "; 
      break; 
     } 
     case 2: { 
      if (to == 0) std::cout << " by bus -> by foot "; 
      if (to == 1) std::cout << " by bus "; 
      if (to == 3) std::cout << " by car "; 
      break; 
     } 
     case 3: { 
      if (to == 1) std::cout << " by car -> by bus "; 
      if (to == 2) std::cout << " by car "; 
      if (to == 0) std::cout << " by air "; 
     } 
    } 

=出発都市です。

〜=私たちが目指している宛先。

解決策は最適ではないと確信していますが、ノードとエッジの数が少ないこの特定のケースでは適用可能です。

Answer 2

あなたは既にこの情報を持って、それがprev_type[x]配列に格納されています。この配列には、最終ノードtに到達するために使用したtransportのタイプが含まれています。これは親ノード、または現在のノードノードに到達したノードノードを覚えているアレイprev[]と組み合わせて機能します。したがって、t（最終ノード）から始めてprev[t]に電話して親を取得し、prev_type[t]にはtに達するのに使用される転送タイプが含まれます。あなたのs（開始）ノードに達するまで、この方法をやり直してください。