Estou certo sobre as diferenças entre Floyd-Warshall, Dijkstra e Bellman-Ford algoritmos?

Question

Tenho estudado três e estou indicando minha inferências a partir deles abaixo.Alguém poderia me dizer se eu entendi corretamente, o suficiente ou não?Obrigado.

1. Dijkstra o algoritmo é usado somente quando você tiver uma única fonte, e você quer conhecer o menor caminho de um nó para outro, mas não em casos como este

2. Floyd-Warshall do algoritmo é utilizado quando qualquer um de todos os nós pode ser uma fonte, de modo que você deseja que a menor distância para chegar a qualquer nó de destino a partir de qualquer nó de origem.Esta falha apenas quando há ciclos negativos

(este é o mais importante.Quero dizer, isso é o que eu tenho menos certeza sobre:)

3.Bellman-Ford é usado como Dijkstra, quando há apenas uma fonte.Isso pode processar negativos pesos e o seu trabalho é o mesmo de Floyd-Warshall s, exceto por uma fonte, certo?

Se você precisa ter um olhar, o correspondente algoritmos (cortesia da Wikipédia):

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

Você está correto sobre as duas primeiras perguntas, e sobre o objetivo de Floyd-Warshall (encontrar o menor caminho entre todos os pares), mas não sobre a relação entre Bellman-Ford e Floyd-Warshall:Ambos os algoritmos utilizar programação dinâmica para encontrar o caminho mais curto, mas FW não é a mesma que executar BF a partir de cada nó inicial para todos os outros nós.

Em BF, a questão é:Qual é o caminho mais curto entre a fonte e o alvo usando, no máximo, k passos, e o tempo de execução é O(EV).Se fosse para executá-lo para outro nó, o tempo de execução seria O(EV^2).

Em FW, a questão é:qual é o caminho mais curto de i a j a k, para todos os nós i,j,k.Isso leva tempo O(V^3) execução de tempo - mais do que o BF para cada nó inicial (por um fator de até |V| para o denso gráficos).

Uma observação mais sobre ciclos negativos / pesos:Dijkstra pode simplesmente deixar de dar os resultados corretos.BF e FW não falha - que vai se corretamente afirmar que não há nenhum peso mínimo caminho, desde que o peso negativo é ligado.

Answer 2

Única fonte caminhos mais:

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

Bellman ford Algoritmo - peso Negativo é permitido.Mas se um ciclo negativo está presente Bellman ford irá detectar a -ve ciclo - O(VE)

Dirigido Acíclico Gráfico - como o nome sugere, ele funciona apenas para o DAG - O(V+E)

Todos os pares de caminhos mais:

Algoritmo Dijkstra - Sem peso negativo permitido - O(VE + V^2lg(V))

Bellman ford Algoritmo - O(V^2E)

Matriz de cadeia de método de multiplicação de complexidade mesmo como Bellman ford algoritmo

Floyd Warshall algoritmo utiliza o método de programação dinâmica - Complexidade é O(V^3)