Czy mam rację co do różnic między algorytmami Floyda-Warshalla, Dijkstry i Bellmana-Forda?

12

Studiowałem te trzy i poniżej przedstawiam swoje wnioski. Czy ktoś mógłby mi powiedzieć, czy dobrze je zrozumiałem, czy nie? Dziękuję Ci.

  1. Algorytm Dijkstry jest używany tylko wtedy, gdy masz jedno źródło i chcesz wiedzieć najmniejszą ścieżkę z jednego węzła do drugiego, ale nie w przypadkach takich jak ten

  2. Algorytm Floyda-Warshalla jest używany, gdy dowolny ze wszystkich węzłów może być źródłem, więc chcesz, aby najkrótsza odległość dotarła do dowolnego węzła docelowego z dowolnego węzła źródłowego. Nie udaje się to tylko wtedy, gdy występują cykle ujemne

(to jest najważniejsze. To jest ten, którego jestem najmniej pewien :)

3.Bellman-Ford jest używany jak Dijkstra, gdy jest tylko jedno źródło. Może to obsługiwać ujemne wagi, a jego działanie jest takie samo jak Floyda-Warshalla, z wyjątkiem jednego źródła, prawda?

Jeśli chcesz rzucić okiem, odpowiednie algorytmy to (dzięki uprzejmości Wikipedii):

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] );
Programowanie Noob
źródło
Jestem prawie pewien, że algorytm Dijkstry radzi sobie z węzłami o ujemnej wadze. Jeżeli występują cykle ujemne, najkrótsza ścieżka jest niezdefiniowana, niezależnie od algorytmu.
kevin cline
1
@kevincline: Wikipedia nie obsługuje twojego roszczenia (nie twierdzę jednak, że wikipedia ma rację, i mam książkę AlgTheory kilkaset mil stąd) Jednak w rzeczywistych problemach z routingiem opartym na czasie lub prędkości występują bez negatywnych krawędzi, więc zwykle robię Dijsktra lub Floyd, w zależności od potrzeby. O ile pamiętam, większość prawdziwych algogramów trasowania kartograficznego opiera się na zmodernizowanej wersji Dijsktry, ale pamiętam to tylko z niektórych artykułów naukowych, które przeczytałem w poprzednim miejscu pracy.
Aadaam
@Aadaam: się mylę. Dijkstra wykorzystuje nie-negatywność, aby uniknąć odwiedzania każdej krawędzi.
kevin cline
Tak, zrozumiałeś poprawnie. :)
Sanghyun Lee

Odpowiedzi:

3

Jeśli dobrze cię rozumiem, twoje zrozumienie jest prawidłowe.

  • Djikstra's znajduje najmniejszą ścieżkę kosztów od węzła źródłowego do każdego innego węzła na wykresie, chyba że istnieje ujemna krawędź wagi. (Dijkstry można łatwo przekształcić w algorytm A *, po prostu zmieniając go, aby zatrzymać po znalezieniu węzła docelowego i dodając heurystykę).
  • Bellman-Ford robi to samo co Dijkstry, ale działa wolniej. Ale może obsługiwać krawędzie o ujemnej wadze.
  • Floyd-Warshall znajduje koszt najmniejszej ścieżki kosztów z każdego węzła do każdego innego węzła. (Zwraca matrycę numeryczną.) Jest znacznie wolniejszy niż Djikstry lub Bellmana-Forda. W przeciwieństwie do tego, co napisałeś, nie zawiedzie, gdy wystąpi cykl ujemny, po prostu zgłasza bez znaczenia liczbę ujemną dla kosztu jakiegoś węzła.
Ceasar Bautista
źródło
1
Nie, Floyd-Warshall może sami obliczyć ścieżki, tak samo jak Djikstra i Bellman-Ford, nie tylko długości ścieżek.
Konrad Rudolph
Oczywiście z modyfikacjami.
Ceasar Bautista
3
Nadal uważałbym ten pierwszy za należący do Dijkstry, gdyby został zatrzymany w węźle docelowym, ale nie używał heurystyki.
Eliot Ball,
1
@CSA - Floyd Warshall ma wartość O (n ^ 3), więc dla tak dużego wykresu potrzeba około 10 ^ 300 operacji. Zakładając, że każda operacja zajmie czas Plancka, do czasu zakończenia obliczeń wszystkie protony w regularnej materii we wszechświecie ulegną rozpadowi i pozostaną tylko supermasywne czarne dziury . Uważam, że możliwe jest zrównoleglenie wewnętrznej pętli. Jeśli to prawda, możesz mieć szczęście, że skończysz, zanim wszystkie czarne dziury, które zaczęły się od masy Słońca, wyparują.
Jules
1
(Zakładając, że możesz zbudować węzeł przetwarzający, używając mniej niż jednego atomu na proces, i możesz użyć wszystkich atomów w obserwowalnym wszechświecie, to znaczy ... ale wtedy prawdopodobnie potrzebujesz wszystkich tych do przechowywania danych na początek)
Jules