Kürzeste Routenänderung

Question

Gibt es eine Möglichkeit dies zu ändern, um die Route des kürzesten Pfades anzuzeigen? Zum Beispiel, wenn ich eine Liste von Zahlen wie (3,1), (3,0), (4,3), (2,1) hätte, wäre die Ausgabe zum Erhalten von 4 zu 1 4> 3,3 -> 1

// Prints shortest paths from src to all other vertices 
void Graph::shortestPath(int src) 
{ 
    // Create a priority queue to store vertices that 
    // are being preprocessed. This is weird syntax in C++. 
    // Refer below link for details of this syntax 
    // http://geeksquiz.com/implement-min-heap-using-stl/ 
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq; 


    // Create a vector for distances and initialize all 
    // distances as infinite (INF) 
    vector<int> dist(V, INF); 

    // Insert source itself in priority queue and initialize 
    // its distance as 0. 
    pq.push(make_pair(0, src)); 
    dist[src] = 0; 

    /* Looping till priority queue becomes empty (or all 
     distances are not finalized) */ 
    while (!pq.empty()) 
    { 
     // The first vertex in pair is the minimum distance 
     // vertex, extract it from priority queue. 
     // vertex label is stored in second of pair (it 
     // has to be done this way to keep the vertices 
     // sorted distance (distance must be first item 
     // in pair) 
     int u = pq.top().second; 
     pq.pop(); 

     // 'i' is used to get all adjacent vertices of a vertex 
     list< pair<int, int> >::iterator i; 
     for (i = adj[u].begin(); i != adj[u].end(); ++i) 
     { 
      // Get vertex label and weight of current adjacent 
      // of u. 
      int v = (*i).first; 
      int weight = (*i).second; 

      // If there is shorted path to v through u. 
      if (dist[v] > dist[u] + weight) 
      { 
       // Updating distance of v 
       dist[v] = dist[u] + weight; 
       pq.push(make_pair(dist[v], v)); 
      } 
     } 
    } 

    // Print shortest distances stored in dist[] 
    printf("Vertex Distance from Source\n"); 
    for (int i = 0; i < V; ++i) 
      printf("%d \t\t %d\n", i, dist[i]); 
    } 

in einem Array Einlochen, die die Zahlen des Wegs wie 4,3,3,1 (mit obigem Beispiel) speichern scheint die beste Idee, aber ich weiß nicht, wo die Array einfügen in diesem Code, um das zu tun.

Answer 1

Speichern Sie die Abstände für jeden Eckpunkt im Vektor dist so, dass Sie den Vorgängerknoten, der ihn zuletzt aktualisiert hat, in einem Vektor namens predecessor speichern.

vector<int> dist(V, INF); 
vector<int> predecessor(V, 0); 

Dann, wenn Sie den Abstand aktualisieren, aktualisieren Sie die Vorgänger:

dist[v] = dist[u] + weight; 
predecessor[v] = u; 

Schließlich können Sie für jeden Vertex verfolgen den kürzesten Weg (rückwärts) mit der Quelle:

printf("Vertex Distance from Source  shortest path from source\n"); 
for (int i = 0; i < V; ++i) 
{ 
     printf("%d \t\t %d\t\t", i, dist[i]); 
     int j = i; 
     do 
     { 
      printf("%d,", j); 
      j = predecessor[j]; 
     } while(j != src); 
     printf("\n"); 
} 

Answer 2

Klingt wie ein Hausaufgaben-Problem.

Ihre Idee, die Nummern des Pfades zu speichern, wäre großartig, wenn das ein DFS wäre. Leider verfolgt Djikstras Algorithmus den Pfad natürlich nicht wie ein DFS; es nimmt einfach den nächstliegenden Knoten und aktualisiert die Entfernungswerte. In dieser Hinsicht ähnelt es wahrscheinlich eher einem BFS.

Was Sie tun könnten ist, wie Sie die Entfernungen zu jedem Knoten aktualisieren, irgendwie speichern, welchen Knoten Sie kommen (vielleicht in Ihrer iPair Struktur, wenn Sie dürfen, vielleicht in einer Karte/Array, wenn Sie eine haben Möglichkeit, Ihre Knoten zu identifizieren). Ich werde es eine "von" Referenz für diesen Beitrag nennen. Jedes Mal, wenn Sie einen kürzeren Pfad zu einem Knoten finden, können Sie diesen auch aus Referenz aktualisieren.

Wie finden Sie dann den Pfad zu einem bestimmten Knoten? Ganz einfach: Beginne einfach am Endknoten und folge den "from" Referenzen zurück zur Quelle.