algorithm
Floyd-Warshall 알고리즘

모든 쌍 최단 경로 알고리즘

Floyd-Warshall 의 알고리즘은 양 또는 음의 에지 가중치가있는 가중 그래프에서 최단 경로를 찾는 알고리즘입니다. 알고리즘을 한 번 실행하면 모든 꼭지점 쌍 사이의 최단 경로 길이 (합계 가중치)를 찾을 수 있습니다. 약간의 변형으로 최단 경로를 인쇄하고 그래프에서 음수 사이클을 감지 할 수 있습니다. Floyd-Warshall은 동적 프로그래밍 알고리즘입니다.

예를 살펴 보겠습니다. 이 그래프에서 Floyd-Warshall의 알고리즘을 적용 할 것입니다.

우선 우리는 두 개의 2D 행렬을 취합니다. 이것들은 인접 행렬 입니다. 행렬의 크기는 정점의 총 수입니다. 우리의 그래프에서 우리는 4 * 4 행렬을 취할 것입니다. Distance Matrix 는 두 정점 사이에서 지금까지 발견 된 최소 거리를 저장합니다. 처음에는 가장자리에 대해 uv 와 거리 / 무게 사이의 가장자리가 있으면 w 를 저장합니다. distance[u][v] = w . 존재하지 않는 모든 가장자리에 대해 우리는 무한을 넣을 것입니다. 경로 매트릭스 는 두 정점 사이의 최소 거리 경로를 재생성하기위한 것입니다. 그래서 처음에는 u 와 v 사이에 경로가 있다면 path[u][v] = u 를 넣을 것입니다. 즉, vertex-u 에서 vertex- v 로 오는 가장 좋은 방법은 v 와 u 를 연결하는 가장자리를 사용하는 것입니다. 두 꼭지점 사이에 경로가 없으면 N 을 입력하여 현재 사용할 수있는 경로가 없음을 나타냅니다. 그래프의 두 테이블은 다음과 같습니다.

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

루프가 없으므로 대각선은 N 으로 설정됩니다. 그리고 정점 자체와의 거리는 0 입니다.

Floyd-Warshall 알고리즘을 적용하기 위해 중간 정점 k 를 선택합니다. 그런 다음 각 꼭지점 i 에 대해 i 에서 k까지 , 그리고 k 에서 j 로 갈 수 있는지 확인합니다. 여기서 j 는 다른 꼭지점이며 i 에서 j 로가는 비용을 최소화합니다. 현재 거리 [i] [j] 가 distance [i] [k] + distance [k] [j] 보다 큰 경우 distance [i] [j]를 이 두 거리의 합계와 같게 지정합니다 . 그리고 경로 [i] [j] 는 경로 [k] [j] 로 설정 될 것입니다. i 에서 k 로 이동 한 다음 k 에서 j 로 이동하는 것이 좋습니다. 모든 정점이 k 로 선택됩니다. 우리는 3 개 중첩 루프를해야합니다 : 1에서 4로가는 k에 대한, 내가 1 일부터 4 일에서 우리는 수표를 겁니다 4. 갈 J으로 이동 :

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

그래서 우리가 기본적으로 검사하는 것은 모든 꼭지점 쌍에 대해 다른 꼭지점을 통과함으로써 더 짧은 거리를 얻는 것입니까? 그래프의 총 작업 수는 4 * 4 * 4 = 64 입니다. 즉, 우리는이 수표를 64 번 할 것입니다. 그 중 몇 가지를 살펴 보겠습니다.

때 K = 1, i가 = 2, J = 3, 거리가 [I] [J] 거리보다 크지 이는 -2 [I] [K] +의 거리 [K] [J] = -2 + 0 = -2 . 그래서 그것은 변하지 않을 것입니다. 또, K = 1, 난 = 4, J = 2, 거리 [I] [J]를 거리보다 큰 무한대 = 때 [I] [K] +의 거리 [K] [J] = 1 + 3 = 4 . 그래서 우리는 distance [i] [j] = 4 를 놓고 path [i] [j] = path [k] [j] = 1을 넣습니다. 이 말은 꼭지점 4 에서 꼭짓점 2 로 가려면 4-> 1-> 2 경로가 기존 경로보다 짧아야한다는 것입니다. 이것이 우리가 두 행렬을 채우는 방법입니다. 각 단계에 대한 계산이 여기 에 표시 됩니다 . 필요한 변경을 한 후에, 우리의 행렬은 다음과 같이 보입니다.

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

이것은 우리의 최단 거리 매트릭스입니다. 예를 들어, 1 에서 4 까지의 최단 거리는 3 이고 4 와 3 사이의 최단 거리는 2 입니다. 우리의 의사 코드는 다음과 같습니다.

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

경로 인쇄 :

경로를 인쇄하려면 경로 행렬을 확인합니다. u 에서 v 까지 경로를 인쇄하려면 경로 [u] [v] 부터 시작합니다. 우리는 변화하는 V = 경로를 계속 설정합니다 [유] [V] 우리가 찾을 때까지 경로 [U] [V] = U를하고 [U] [V] 스택에 경로의 모든 값을 누릅니다. U를 발견하고 난 후에, 우리는 U를 인쇄하고이를 스택에서 항목을 보여주고 시작하고 인쇄 할 수 있습니다. 이것은 경로 행렬이 다른 노드의 v에 대한 최단 경로를 공유하는 정점의 값을 저장하기 때문에 작동합니다. 의사 코드는 다음과 같습니다.

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

네거티브 에지 사이클 찾기 :

네거티브 에지 사이클이 있는지 알아 보려면 거리 매트릭스의 주 대각선을 확인해야합니다. 대각선의 값이 음수이면 그래프에 음수 사이클이 있음을 의미합니다.

복잡성:

Floyd-Warshall 알고리즘의 복잡성은 O (V³) 이고 공간 복잡도는 O (V²) 입니다.