Ho ragione sulle differenze tra Floyd-Warshall, Algoritmi di Dijkstra e Bellman-Ford?

Question

Ho studiato i tre e sto affermando le mie inferenze da loro di seguito. Qualcuno potrebbe dirmi se li ho capiti abbastanza o meno? Grazie.

.

1. L'algoritmo di Dijkstra è usato solo quando si ha una singola fonte e si desidera conoscere il percorso più piccolo da un nodo all'altro, ma fallisce nei casi come questo

2. L'algoritmo Floyd-Warshall viene utilizzato quando uno qualsiasi di tutti i nodi può essere un'origine, in modo da desiderare la distanza più breve per raggiungere qualsiasi nodo di destinazione da qualsiasi nodo di origine. Questo fallisce solo quando ci sono cicli negativi

(questo è il più importante. Voglio dire, questo è quello di cui meno di :)

3.bellman-Ford è usato come dijkstra, quando c'è solo una fonte. Questo può gestire pesi negativi e il suo funzionamento è lo stesso di Floyd-Warshall ad eccezione di una fonte, giusto?

Se è necessario dare un'occhiata, gli algoritmi corrispondenti sono (cortesia 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

Sei corretto sulle prime due domande e sull'obiettivo di Floyd-Warshall (trovando i percorsi più brevi tra tutte le coppie), ma non riguardo alla relazione tra Bellman-Ford e Floyd-Warshall: entrambi gli algoritmi usano la programmazione dinamica a Trova il percorso più breve, ma FW non è lo stesso di eseguire BF da ciascun nodo di avvio ad ogni altro nodo.

In BF, la domanda è: qual è il percorso più breve dalla fonte al bersaglio usando al massimo i gradini e il tempo di esecuzione è O (E V). Se dovessimo esecurlo l'altro nodo, il tempo di esecuzione sarebbe O (E V ^ 2).

In FW, la domanda è: qual è il percorso più breve da I to J a K attraverso K, per tutti i nodi I, J, K. Questo porta a O (V ^ 3) Tempo di esecuzione - Meglio di BF per ciascun nodo Avvio (con un fattore fino a | V | per grafici densi).

Un'altra nota sui cicli negativi / pesi: Dijkstra potrebbe semplicemente non fornire i risultati corretti. BF e FW non riusciranno a fallire: affermano correttamente che non esiste un percorso di peso minimo, poiché il peso negativo è illimitato.

Answer 2

Sorgente singola Percorsi più brevi:

Dijkstra Algoritmo - Nessun peso negativo consentito - O (E + VLG (V))

Bellman Ford Algoritmo - Il peso negativo è consentito.Ma se è presente un ciclo negativo che Bellman Ford rileverà il ciclo -ve-o (VE)

Grafico acyclico diretto - Come suggerisce il nome funziona solo per DAG - O (V + E)

Tutte le coppie percorsi più corti:

Algoritmo Dijkstra - Nessun peso negativo consentito - O (VE + V ^ 2LG (V))

Bellman Ford Algoritmo - O (V ^ 2E)

Metodo di moltiplicazione della catena della matrice -Complessità come Bellman Ford Algoritmo

Floyd Warshall Algoritmo - Metodo di programmazione dinamico Dynamic - La complessità è O (V ^ 3)