¿Tengo razón en las diferencias entre los algoritmos de Floyd-Warshall, Dijkstra y Bellman-Ford?

Question

He estado estudiando los tres y estoy diciendo mis inferencias a continuación. ¿Podría alguien decirme si los he entendido con la suficiente precisión o no? Gracias.

1. algoritmo de Dijkstra se utiliza sólo cuando se tiene una sola fuente y desea conocer la ruta más pequeña de un nodo a otro, pero fracasa en casos como this

algoritmo

2. de Floyd-Warshall se utiliza cuando cualquiera de los nodos puede ser una fuente, por lo que desea la distancia más corta para llegar a cualquier nodo de destino desde cualquier nodo de origen. Esto sólo falla cuando hay ciclos negativos

(este es el más importante. Es decir, este es el que estoy menos seguro sobre :)

3.Bellman-Ford es usado como el de Dijkstra, cuando solo hay una fuente. Esto puede manejar pesos negativos y su funcionamiento es el mismo que el de Floyd-Warshall excepto por una fuente, ¿no?

Si es necesario tener una mirada, los algoritmos correspondientes son (cortesía de 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]); 

Answer 1

Tiene razón sobre las dos primeras preguntas y sobre el objetivo de Floyd-Warshall (encontrar los caminos más cortos entre todos los pares), pero no sobre la relación entre Bellman-Ford y Floyd-Warshall: ambos algoritmos usan programación dinámica para encontrar la ruta más corta, pero FW no es lo mismo que ejecutar BF desde cada nodo inicial a cada otro nodo.

En BF, la pregunta es: ¿Cuál es la ruta más corta desde la fuente al destino utilizando como máximo k pasos, y el tiempo de ejecución es O (E V). Si tuviéramos que ejecutarlo a cada otro nodo, el tiempo de ejecución sería O (E V^2).

En FW, la pregunta es: ¿cuál es el camino más corto de i a j a k, para todos los nodos i, j, k. Esto lleva a O (V^3) tiempo de funcionamiento - mejor que BF para cada nodo inicial (por un factor de hasta | V | para gráficos densos).

Una nota más sobre los ciclos/pesos negativos: Dijkstra puede simplemente no dar los resultados correctos. BF y FW no fallarán: indicarán correctamente que no hay una ruta de peso mínima, ya que el peso negativo no tiene límites.

Answer 2

fuente individual caminos más cortos:

Algoritmo de Dijkstra - No peso negativo permitido - O (E + Vlg (V))

Bellman Ford Algoritmo - se permite peso negativo.Pero si un ciclo negativo está presente Bellman Ford detectará el ciclo -ve - O (VE)

Dirigido acíclicos Gráfico - como su nombre indica, sólo funciona para DAG - O (V + E)

Todos los pares cortos caminos:

Dijkstra Algoritmo - No peso negativo permitido - O (VE + V^2LG (V))

Bellman Ford Algoritmo - O (V^2E)

Matrix método de la multiplicación cadena --complejidad mismo como el algoritmo de Ford Belld

método de programación dinámica

Floyd Warshall algoritmo: utiliza - La complejidad es O (V^3)