Linearer Zeit Graphalgorithmus

Question

Gibt es einen ungerichteten GraphG = (V, E), gibt es einen Algorithmus, der die Gesamtzahl der kürzesten Wege zwischen zwei beliebigen Ecken berechnet?v? Ich denke, wir können den Algorithmus von Dijkstra verwenden.

Answer 1

Ja können Sie Dijkstra verwenden. Erstellen Sie ein Array, das die Gesamtanzahl des kürzesten Pfads zu einem beliebigen Knoten speichert. Nenne es total. Der Anfangswert aller Array-Elemente ist 0, mit Ausnahme von total [s] = 1, wobei s die Quelle ist. In der Dijkstra-Schleife wird beim Aktualisieren des kleinsten Pfads eines Knotens, wenn das Ergebnis der Vergleichung kleiner ist, das gesamte Array dieses Knotens mit der Anzahl der gesamten aktuellen Knoten aktualisiert.

Wenn es gleich ist, addiere das gesamte Array dieses Knotens mit der Anzahl der gesamten aktuellen Knoten.

Pseudocode aus wikipedia mit einigen Änderungen wurde:

function Dijkstra(Graph, source): 

    create vertex set Q 

    for each vertex v in Graph:    // Initialization 
     dist[v] ← INFINITY     // Unknown distance from source to v 
     total[v] ← 0      // total number of shortest path 
     add v to Q       // All nodes initially in Q (unvisited nodes) 

    dist[source] ← 0      // Distance from source to source 
    total[source] ← 1      // total number of shortest path of source is set to 1 

    while Q is not empty: 
     u ← vertex in Q with min dist[u] // Source node 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 
       total[v] ← total[u]   // update the total array of that node with the number of total array of current node 
      elseif alt = dist[v] 
       total[v] ← total[v] + total[u] // add the total array of that node with the number of total array of current node 

    return dist[], total[]