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

floyd warshall python

Question

He estado estudiando los tres y estoy exponiendo mis inferencias de ellos a continuación. ¿Alguien podría decirme si los he entendido con suficiente precisión o no? Gracias.

1. El algoritmo de Dijkstra se usa solo cuando tiene una sola fuente y desea conocer la ruta más pequeña de un nodo a otro, pero falla en casos como this

2. El algoritmo de Floyd-Warshall se usa cuando cualquiera de los nodos puede ser una fuente, por lo que desea que la distancia más corta llegue a cualquier nodo de destino desde cualquier nodo fuente. Esto solo falla cuando hay ciclos negativos

(este es el más importante. Quiero decir, este es el tema del que estoy menos seguro :)

3.Bellman-Ford se usa 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, ¿verdad?

Si necesita echar un vistazo, 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 la programación dinámica para encontrar el más corto ruta, pero FW no es lo mismo que ejecutar BF desde cada nodo de inicio a cada otro nodo.

En BF, la pregunta es: ¿Cuál es la ruta más corta desde la fuente hasta el destino utilizando, como máximo, k pasos, y el tiempo de ejecución es O (E V). Si tuviéramos que ejecutarlo en 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 al tiempo de ejecución de O (V ^ 3), mejor que BF para cada nodo de inicio (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ínimo, ya que el peso negativo no tiene límites.

Answer 2

Trayectorias más cortas de una sola fuente:

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

Bellman ford Algorithm - Se permite peso negativo. Pero si hay un ciclo negativo, Bellman ford detectará el ciclo -ve - O (VE)

Dirigido Acyclic Graph - como su nombre indica, solo funciona para DAG - O (V + E)

Todos los pares de caminos más cortos:

Algoritmo de Dijkstra - No se permite peso negativo - O (VE + V ^ 2lg (V))

Bellman ford Algorithm - O (V ^ 2E)

Método de multiplicación de la cadena matricial: la misma complejidad que el algoritmo de Bellman Ford

Algoritmo de Floyd Warshall, que utiliza el método de programación dinámica, la complejidad es O (V ^ 3)