Habe ich Recht mit den Unterschieden zwischen Floyd-Warshall-, Dijkstra- und Bellman-Ford-Algorithmen?

12

Ich habe die drei studiert und gebe meine Schlussfolgerungen von ihnen weiter unten an. Kann mir jemand sagen, ob ich sie richtig verstanden habe oder nicht? Vielen Dank.

  1. Dijkstra-Algorithmus wird nur dann verwendet , wenn Sie eine Hand haben , und Sie wollen den kleinsten Pfad von einem Knoten zum anderen kennen, aber nicht in Fällen wie diesen

  2. Der Floyd-Warshall-Algorithmus wird verwendet, wenn einer der Knoten eine Quelle sein kann. Sie möchten also, dass die kürzeste Entfernung von einem Quellknoten zu einem beliebigen Zielknoten besteht. Dies schlägt nur bei negativen Zyklen fehl

(Dies ist das wichtigste. Ich meine, das ist das, bei dem ich mir am wenigsten sicher bin :)

3. Bellman-Ford wird wie Dijkstra verwendet, wenn es nur eine Quelle gibt. Dies kann mit negativen Gewichten und umgehen funktioniert genauso wie bei Floyd-Warshall mit Ausnahme einer Quelle, oder?

Wenn Sie einen Blick darauf werfen müssen, sind die entsprechenden Algorithmen (mit freundlicher Genehmigung von Wikipedia):

Bellman-Ford:

 procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge uv in edges: // uv is the edge from u to v
           u := uv.source
           v := uv.destination
           if u.distance + uv.weight < v.distance:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           error "Graph contains a negative-weight cycle"

Dijkstra:

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from 
 4                                                                 // source to v
 5          previous[v] := undefined ;                             // Previous node in optimal path
 6                                                                 // from source
 7      
 8      dist[source] := 0 ;                                        // Distance from source to source
 9      Q := the set of all nodes in Graph ;                       // All nodes in the graph are
10                                                                 // unoptimized - thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
13          if dist[u] = infinity:
14              break ;                                            // all remaining vertices are
15                                                                 // inaccessible from source
16          
17          remove u from Q ;
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                                 removed from Q.
20              alt := dist[u] + dist_between(u, v) ;
21              if alt < dist[v]:                                  // Relax (u,v,a)
22                  dist[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25      return dist;

Floyd-Warshall:

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
 9    edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
Noob programmieren
quelle
Ich bin mir ziemlich sicher, dass der Dijkstra-Algorithmus Knoten mit negativer Gewichtung verarbeiten kann. Bei Zyklen mit negativer Gewichtung ist der kürzeste Pfad unabhängig vom Algorithmus nicht definiert.
Kevin Cline
1
@kevincline: Wikipedia unterstützt Ihre Behauptung nicht (ich behaupte jedoch nicht, dass Wikipedia richtig ist und ich habe mein AlgTheory-Buch ein paar hundert Meilen entfernt). In Echtzeit gibt es jedoch zeit- oder geschwindigkeitsbezogene Routing-Probleme Keine negativen Flanken, also mache ich normalerweise Dijsktra oder Floyd, je nach Bedarf. Soweit ich mich erinnere, basieren die meisten realen kartografischen Routingalgen auf einer modernisierten Version von Dijsktra, aber ich erinnere mich nur an einige wissenschaftliche Artikel, die ich an meinem früheren Arbeitsplatz gelesen habe.
Aadaam
@Aadaam: Ich irre mich. Dijkstra nutzt die Nicht-Negativität aus, um nicht jede Kante zu besuchen.
Kevin Cline
Ja, Sie haben richtig verstanden. :)
Sanghyun Lee

Antworten:

3

Wenn ich Sie richtig verstehe, ist Ihr Verständnis richtig.

  • Djikstra's findet den kleinsten Kostenpfad von einem Quellknoten zu jedem anderen Knoten in der Grafik, außer wenn es eine negative Gewichtungskante gibt. (Dijkstra's können einfach in den A * -Algorithmus umgewandelt werden, indem man ihn so ändert, dass er stoppt, sobald er den Zielknoten gefunden und Heuristiken hinzugefügt hat.)
  • Bellman-Ford macht dasselbe wie Dijkstra, ist aber langsamer. Aber es kann negative Gewichtsränder verarbeiten.
  • Floyd-Warshall ermittelt die Kosten für den kleinsten Kostenpfad von jedem Knoten zu jedem anderen Knoten. (Es gibt eine numerische Matrix zurück.) Sie ist weitaus langsamer als die von Djikstra oder Bellman-Ford. Im Gegensatz zu dem, was Sie geschrieben haben, schlägt es nicht fehl, wenn ein negativer Zyklus auftritt, sondern meldet nur eine bedeutungslose negative Zahl für die Kosten eines Knotens an sich.
Caesar Bautista
quelle
1
Nein, Floyd-Warshall kann die Pfade selbst berechnen, genauso wie Djikstra und Bellman-Ford, nicht nur die Pfadlängen.
Konrad Rudolph
Natürlich mit Modifikationen.
Ceasar Bautista
3
Ich würde immer noch als erstes Dijkstra betrachten, wenn es an einem Zielknoten gestoppt wäre, aber keine Heuristik verwendet.
Eliot Ball
1
@CSA - Floyd Warshall ist O (n ^ 3), daher wären für einen so großen Graphen etwa 10 ^ 300 Operationen erforderlich. Angenommen, jede Operation benötigt Planck-Zeit. Bis die Berechnung abgeschlossen ist, sind alle Protonen in der regulären Materie im Universum zerfallen und es bleiben nur noch supermassereiche Schwarze Löcher übrig . Ich glaube, es ist möglich, die innere Schleife zu parallelisieren. Wenn dies zutrifft, haben Sie möglicherweise das Glück, fertig zu werden, bevor alle schwarzen Löcher, die mit der Sonnenmasse begannen, verdunstet sind.
Jules
1
(Angenommen, Sie können einen Verarbeitungsknoten mit weniger als einem Atom pro Prozess erstellen und alle Atome im beobachtbaren Universum verwenden, das heißt ... aber dann benötigen Sie wahrscheinlich alle diese, um Ihre Daten zu speichern.)
Jules