Est-ce que j'ai raison sur les différences entre les algorithmes de Floyd-Warshall, de Dijkstra et de Bellman-Ford?

Question

J'ai étudié les trois et je déclare mes inférences d'eux ci-dessous. Quelqu'un pourrait-il me dire si je les ai compris avec précision ou pas? Merci.

1. L'algorithme de Dijkstra n'est utilisé que lorsque vous avez une source unique et que vous souhaitez connaître le plus petit chemin d'un nœud à un autre, mais échoue dans des cas comme Ce

2. L'algorithme de Floyd-Warshall est utilisé lorsque l'un de tous les nœuds peut être une source, vous souhaitez donc que la distance la plus courte atteigne n'importe quel nœud de destination à partir de n'importe quel nœud source. Cela échoue seulement quand il y a des cycles négatifs

(c'est le plus important. Je veux dire, c'est celui que je suis le moins sûr de :)

3.Bellman-Ford est utilisé comme celui de Dijkstra, quand il n'y a qu'une seule source. Cela peut gérer des poids négatifs et son travail est identique à celui de Floyd-Warshall, à l'exception d'une source, non?

Si vous avez besoin d'un look, les algorithmes correspondants sont (courtoisie 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

Vous êtes correct sur les deux premières questions et sur l'objectif de Floyd-Warshall (Trouver les chemins les plus courts entre toutes les paires), mais pas sur la relation entre Bellman-Ford et Floyd-Warshall: les deux algorithmes utilisent une programmation dynamique à Trouvez le chemin le plus court, mais FW n'est pas le même que de courir BF de chaque noeud de départ à tous les autres nœuds.

Dans BF, la question est la suivante: quel est le chemin le plus court de la source à la cible à l'aide de la plupart des étapes k, et le temps d'exécution est O (E V). Si nous devions l'exécuter dans l'autre noeud, le temps de fonctionnement serait O (e v ^ 2).

En FW, la question est la suivante: quel est le chemin le plus court de i à j à k à k, pour tous les nœuds i, j, k. Cela conduit à O (v ^ 3) heure d'exécution - mieux que BF pour chaque noeud de départ (par un facteur allant jusqu'à | V | V | pour des graphiques denses).

Une note de plus sur les cycles / poids négatifs: Dijkstra peut simplement ne pas donner les résultats corrects. BF et FW n'échoueront pas - ils indiqueront correctement qu'il n'y a pas de chemin de poids minimum, car le poids négatif est sans bornes.

Answer 2

Source Source Sentiers les plus courts:

algorithme de dijkstra - Aucun poids négatif autorisé - O (E + VLG (V))

Algorithme Bellman Ford - Le poids négatif est autorisé.Mais si un cycle négatif est présent, Bellman Ford détectera le cycle -ve - O (VE)

Graphique acyclique dirigé - comme le nom le suggère qu'il fonctionne uniquement pour DAG-O (V + E)

Tous les paires chemins les plus courts:

algorithme dijkstra - pas de poids négatif autorisé - o (VE + V ^ 2LG (V))

Bellman Ford Algorithm - O (v ^ 2e)

Méthode de multiplication de la chaîne matricielle - COMPLÉxITÉ MÊME COMME BOBMAN FORD ALGORITHM

algorithme Floyd Warshall - Procédé de programmation dynamique - la complexité est O (v ^ 3)