Floyd-Warshall, Dijkstra 및 Bellman-Ford 알고리즘의 차이점에 대해 제가 맞습니까?

StackOverflow https://stackoverflow.com//questions/11704643

문제

나는 세 가지를 연구해왔고 아래에 그들로부터 추론을 말하고 있습니다.내가 그것들을 충분히 정확하게 이해했는지 누군가가 말해 줄 수 있습니까?감사합니다.

  1. Dijkstra의 알고리즘은 단일 소스가 있고 한 노드에서 다른 노드까지의 가장 작은 경로를 알고 싶을 때만 사용되지만 다음과 같은 경우에는 실패합니다. 이것

  2. Floyd-Warshall의 알고리즘은 모든 노드 중 하나가 소스가 될 수 있으므로 모든 소스 노드에서 대상 노드에 도달하는 최단 거리를 원할 때 사용됩니다.이는 음수 사이클이 있는 경우에만 실패합니다.

(이것이 가장 중요합니다.내 말은, 이것이 내가 가장 확신하지 못하는 것입니다 :)

3. Bellman-Ford는 소스가 하나뿐인 경우 Dijkstra와 마찬가지로 사용됩니다.이는 음의 가중치를 처리할 수 있으며 작동 방식은 소스 하나를 제외하면 Floyd-Warshall과 동일합니다. 그렇죠?

살펴봐야 할 경우 해당 알고리즘은 다음과 같습니다(Wikipedia 제공).

벨먼-포드:

 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"

데이크스트라:

 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;

플로이드-워샬:

 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] );
도움이 되었습니까?

해결책

처음 두 질문과 Floyd-Warshall의 목표(모든 쌍 사이의 최단 경로 찾기)에 대해서는 정확하지만 Bellman-Ford와 Floyd-Warshall 간의 관계에 대해서는 정확하지 않습니다.두 알고리즘 모두 동적 프로그래밍을 사용하여 최단 경로를 찾지만 FW는 각 시작 노드에서 다른 모든 노드까지 BF를 실행하는 것과 동일하지 않습니다.

BF에서 질문은 다음과 같습니다.최대 k 단계를 사용하여 소스에서 대상까지의 최단 경로는 무엇이며 실행 시간은 O(EV).이를 서로 다른 노드로 실행한다면 실행 시간은 O(EV^2).

FW에서 질문은 다음과 같습니다.모든 노드 i,j,k에 대해 i에서 k를 거쳐 j까지의 최단 경로는 무엇입니까?이로 인해 O(V^3) 실행 시간이 발생합니다. 이는 각 시작 노드에 대해 BF보다 우수합니다(밀집 그래프의 경우 최대 |V| 배).

음수 사이클/가중치에 대한 추가 참고사항:Dijkstra는 단순히 올바른 결과를 제공하지 못할 수도 있습니다.BF와 FW는 실패하지 않습니다. 음의 가중치는 제한이 없기 때문에 최소 가중치 경로가 없다고 올바르게 명시합니다.

다른 팁

단일 소스 최단 경로:

Dijkstra 알고리즘 - 음의 가중치가 허용되지 않음 - O(E+Vlg(V))

Bellman ford 알고리즘 - 음의 가중치가 허용됩니다.그러나 음의 사이클이 존재하는 경우 Bellman Ford는 -ve 사이클 - O(VE)를 감지합니다.

방향성 비순환 그래프 - 이름에서 알 수 있듯이 DAG에서만 작동합니다 - O(V+E)

모든 쌍의 최단 경로:

Dijkstra 알고리즘 - 음의 가중치가 허용되지 않음 - O(VE + V^2lg(V))

벨만 포드 알고리즘 - O(V^2E)

행렬 체인 곱셈 방법 - 복잡도는 Bellman ford 알고리즘과 동일

Floyd Warshall 알고리즘 - 동적 프로그래밍 방법 사용 - 복잡도는 O(V^3)입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top