Estou certo sobre as diferenças entre os algoritmos de Floyd-Warshall, Dijkstra e Bellman-Ford?

Eu tenho estudado os três e estou declarando minhas inferências abaixo. Alguém poderia me dizer se eu os entendi com precisão ou não? Obrigado.

1. O algoritmo de Dijkstra é usado apenas quando você tem uma única fonte e deseja conhecer o menor caminho de um nó para outro, mas falha em casos como este

2. O algoritmo de Floyd-Warshall é usado quando qualquer um dos nós pode ser uma fonte, portanto, você deseja que a distância mais curta alcance qualquer nó de destino a partir de qualquer nó de origem. Isso só falha quando há ciclos negativos

(este é o mais importante. Quero dizer, este é o que eu tenho menos certeza :)

3.Bellman-Ford é usado como o de Dijkstra, quando existe apenas uma fonte. Isso pode lidar com pesos negativos e seu trabalho é igual ao de Floyd-Warshall, exceto por uma fonte, certo?

Se você precisar dar uma olhada, os algoritmos correspondentes são (cortesia da 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] );

Se eu entendi corretamente, seu entendimento está correto.

• O Djikstra encontra o menor caminho de custo de um nó de origem para todos os outros nós no gráfico, exceto se houver uma borda de peso negativa. (O Dijkstra pode ser facilmente transformado no algoritmo A *, basta alterá-lo para parar quando encontrar o nó de destino e adicionar heurísticas.)
• Bellman-Ford faz o mesmo que o de Dijkstra, mas é mais lento. Mas ele pode lidar com arestas de peso negativo.
• Floyd-Warshall encontra o custo do menor caminho de custo de cada nó para todos os outros nós. (Ele retorna uma matriz numérica.) É muito mais lento que Djikstra ou Bellman-Ford. Ao contrário do que você escreveu, ele não falha quando ocorre um ciclo negativo, apenas relata um número negativo sem sentido para o custo de algum nó para si mesmo.