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

12

He estado estudiando los tres y estoy declarando mis inferencias de ellos a continuación. ¿Podría alguien decirme si los he entendido con la 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 este

  2. El algoritmo de Floyd-Warshall se usa cuando cualquiera de todos 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 que menos estoy seguro :)

3.Bellman-Ford se usa como 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] );
Programación de novatos
fuente
Estoy bastante seguro de que el algoritmo de Dijkstra puede manejar nodos de peso negativo. Si hay ciclos de peso negativo, la ruta más corta no está definida, independientemente del algoritmo.
Kevin Cline
1
@kevincline: Wikipedia no respalda su reclamo (no estoy afirmando que wikipedia sea correcto, y tengo mi libro AlgTheory a unos cientos de millas de distancia) Sin embargo, en la vida real hay problemas de enrutamiento basados ​​en el tiempo o la velocidad. sin bordes negativos, por lo que generalmente hago Dijsktra o Floyd, dependiendo de la necesidad. Hasta donde recuerdo, la mayoría de los algos de enrutamiento cartográfico de la vida real se basan en la versión modernizada de Dijsktra, pero solo lo recuerdo de algunos artículos científicos que he leído en mi lugar de trabajo anterior.
Aadaam
@Aadaam: estoy equivocado. Dijkstra explota la no negatividad para evitar visitar cada borde.
Kevin Cline
Sí,
entendiste

Respuestas:

3

Si te entiendo correctamente, tu comprensión es correcta.

  • Djikstra encuentra la ruta de costo más pequeña desde un nodo fuente a cualquier otro nodo en el gráfico, excepto si hay un borde de peso negativo. (Dijkstra se puede transformar fácilmente en el algoritmo A * simplemente cambiándolo para que se detenga una vez que encuentre el nodo objetivo y agregue heurística).
  • Bellman-Ford hace lo mismo que Dijkstra, pero es más lento. Pero puede manejar bordes de peso negativos.
  • Floyd-Warshall encuentra el costo de la ruta de costo más pequeña de cada nodo a cualquier otro nodo. (Devuelve una matriz numérica). Es mucho más lenta que la de Djikstra o Bellman-Ford. A diferencia de lo que escribió, no falla cuando ocurre un ciclo negativo, solo informa un número negativo sin sentido para el costo de algún nodo para sí mismo.
Ceasar Bautista
fuente
1
No, Floyd-Warshall puede calcular los caminos ellos mismos, al igual que Djikstra y Bellman-Ford, no solo las longitudes de los caminos.
Konrad Rudolph el
Con modificaciones, por supuesto.
Ceasar Bautista
3
Todavía consideraría que el primero es el de Dijkstra si se detuviera en un nodo objetivo, pero no usara heurística.
Eliot Ball
1
@CSA - Floyd Warshall es O (n ^ 3), por lo que se necesitarían alrededor de 10 ^ 300 operaciones para un gráfico tan grande. Suponiendo que cada operación lleva tiempo de Planck, para cuando el cálculo haya terminado, todos los protones en la materia regular del universo se habrán descompuesto, y solo quedarán agujeros negros supermasivos . Creo que es posible paralelizar el circuito interno. Si esto es cierto, puede tener la suerte de terminar antes de que todos los agujeros negros que comenzaron con la masa del sol se hayan evaporado.
Jules
1
(Suponiendo que puede construir un nodo de procesamiento usando menos de un átomo por proceso, y puede usar todos los átomos en el universo observable, eso es ... pero entonces probablemente necesite todos esos para almacenar sus datos para comenzar)
Jules