Dijikstra計算後のパスの印刷方法は？

Question

私はGraphsアルゴリズムを実装し始めました。このDijkstra実装では、ソースからデスティネーションへのパスをどのように印刷するのか分かりません。 は、ダイクストラを使用すると、設定され、あなたの「訪問したセット」にノードを追加するたびに、あなた

#define INF 0x3f3f3f3f 
typedef pair<int,int> ii; // to vertex, weight 
typedef vector<ii> vii; // from source to vertexes with weight 
typedef vector<vii> graph; // graph 

graph gg; 
vector<int> Dist; 

void Dijikstra(int source, int N){ 
    priority_queue<ii, vii, greater<ii>> Q; 
    Dist.assign(N,INF); 
    Dist[source] = 0; 
    Q.push(make_pair(0,source)); 
    while (!Q.empty()) 
    { 
     ii front = Q.top(); Q.pop(); 
     int d = front.first, u = front.second; 
     if(d > Dist[u]) continue; 
     for (int i = 0; i < gg[u].size(); i++) 
     { 
      ii v = gg[u][i]; 
      if(Dist[u]+v.second < Dist[v.first]){ 
       Dist[v.first] = Dist[u] + v.second; 
       Q.push(ii(Dist[v.first],v.first));   
      } 
     } 
    } 
} 

Answer 1

ありがとうございましたこと、すなわち訪れ、それが追加された介して設定からノードノードの親 'または「起源」、。ターゲットノードに到達したら、そこから始めて、ソースに戻るまで親ノードを元に戻します。

このシーケンスを印刷することから始めたり、より視覚的なアプローチを探している場合は、ツールとライブラリのgraphvizセットを見ることができます。

Answer 2

ダイクストラのアルゴリズムの擬似コード：

function Dijkstra(Graph, source): 
    create vertex set Q 
    for each vertex v in Graph: // Initialization 
     dist[v] ← INFINITY  // Unknown distance from source to v 
     prev[v] ← UNDEFINED  // Previous node in optimal path from source 
     add v to Q    // All nodes initially in Q (unvisited nodes) 
    dist[source] ← 0    // Distance from source to source 
    while Q is not empty: 
     u ← vertex in Q with min dist[u] // Node with the least distance will be selected first 
     remove u from Q  
     for each neighbor v of u:   // where v is still in Q. 
      alt ← dist[u] + length(u, v) 
      if alt < dist[v]:    // A shorter path to v has been found 
       dist[v] ← alt 
       prev[v] ← u 
    return dist[], prev[] 

はパスを再構築：

S ← empty sequence 
u ← target 
while prev[u] is defined:   // Construct the shortest path with a stack S 
    insert u at the beginning of S // Push the vertex onto the stack 
    u ← prev[u]      // Traverse from target to source 
insert u at the beginning of S  // Push the source onto the stack