Apakah saya benar tentang perbedaan antara algoritma Floyd-Warshall, Dijkstra dan Bellman-Ford?

Saya telah mempelajari ketiganya dan saya menyatakan kesimpulan saya dari mereka di bawah ini. Bisakah seseorang memberi tahu saya jika saya sudah memahaminya dengan cukup akurat atau tidak? Terima kasih.

1. Algoritma Dijkstra hanya digunakan ketika Anda memiliki satu sumber dan Anda ingin tahu jalur terkecil dari satu node ke yang lain, tetapi gagal dalam kasus seperti ini

2. Algoritma Floyd-Warshall digunakan ketika salah satu dari semua node dapat menjadi sumber, sehingga Anda ingin jarak terpendek untuk mencapai simpul tujuan dari simpul sumber apa pun. Ini hanya gagal ketika ada siklus negatif

(ini yang paling penting. Maksudku, ini yang paling tidak aku yakini :)

3.Bellman-Ford digunakan seperti Dijkstra, ketika hanya ada satu sumber. Ini dapat menangani bobot negatif dan kerjanya sama dengan Floyd-Warshall kecuali untuk satu sumber, bukan?

Jika Anda perlu melihatnya, algoritme yang sesuai adalah (milik 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] );

Jika saya mengerti Anda dengan benar, pengertian Anda benar.

• Djikstra's menemukan jalur biaya terkecil dari node sumber ke setiap node lain dalam grafik, kecuali jika ada tepi bobot negatif. (Dijkstra's dapat ditransformasikan dengan mudah menjadi algoritma A * hanya dengan mengubahnya untuk berhenti setelah menemukan node target dan menambahkan heuristik.)
• Bellman-Ford melakukan hal yang sama dengan Dijkstra, tetapi lebih lambat. Tetapi dapat menangani tepi berat negatif.
• Floyd-Warshall menemukan biaya jalur biaya terkecil dari setiap node ke setiap node lainnya. (Ini mengembalikan matriks numerik.) Jauh lebih lambat daripada Djikstra atau Bellman-Ford. Tidak seperti apa yang Anda tulis, itu tidak gagal ketika siklus negatif terjadi, itu hanya melaporkan angka negatif yang tidak berarti untuk biaya beberapa node untuk dirinya sendiri.