Как распечатать путь после расчета Диджикстры?

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