최단 경로 - 플로이드 워셜 알고리즘

다익스트라

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 

 

정의에서 살펴볼 수 있듯이 한 지점이 아닌 '모든 지점' 에서 다른 모든 지점까지의 최단 경로를 모두 구하는 것이 플로이드 워셜 알고리즘이다. 

 

 

다익스트라가 1차원 배열에 최단 거리를 저장했다면, 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장해야 한다. (다익스트라는 특정 점부터의 거리만 저장하면 되었지만 플로이드 워셜은 각 노드에서 각 노드로 가는 거리를 인접 행렬에 작성해야 한다.)

 

각 단계에서 해당 노드를 거쳐가는 경우를 고려

 

1번 노드에 대해서 확인할 경우: 1번 노드를 중간에 거쳐 지나가는 모든 경우 고려

A $\rightarrow$ 1 번 노드 $\rightarrow$ B 

기존 A $\rightarrow$ B 의 비용과 비교하여 비용 갱신 

 

해당 내용만 보면 다익스트라에서도 수행 될 수 있는 경우이기에 감이 잘 안온다. 

 

정리하자면, 플로이드 워셜 알고리즘은 현재 확인 하고있는 노드를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B)를 선택하고, A $\rightarrow$ 1 번 노드 $\rightarrow$ B로 가는 비용을 확인한 뒤 최단 거리를 갱신한다. 

 

주어진 각 노드에 연결 상태를 인접 행렬에 업데이트 한다. 

모든 노드를 방문하며, 그때마다 한 거리씩 경로 범위가 확대된다. 

어떤 노드 순서로 방문해도 한거리씩 경로 범위가 확대되다보면 결국 노드와 가장 거리가 멀리 떨어져 있는 노드까지도 거리가 업데이트 된다. 아래와 같은 예시가 있다고 하자.

• 첫 번째 그림과 같이, 하나의 노드(파란 노드)를 선택한다.
• 두 번째 그림과 같이, 파란 노드를 기준으로 인근 노드(연보라)들 끼리의 거리 비용을 확인한다. 
• 세 번째 그림과 같이, 서로의 거리를 확인한 노드를 노란색으로 표기하였다. 새롭게 하나의 노드(파란 노드)를 선택한 후, 인근 노드들 끼리의 거리 비용을 확인한다. 그전 단계에서 인근 노드 비용 확인을 통해 1칸 이상 떨어진 노드와의 거리 비용을 확인하였다. 
• 네 번째 그림과 같이, 1칸 이상 떨어져 있던 노드(선택된 노란 노드)와 새로운 인근 노드(선택된 연보라 노드)의 거리 비용을 계산할 수 있게 되었다. 

모든 노드에서 인근 노드의 거리를 확인하는 과정에서 최단 거리도 업데이트 된다. 
얕게 생각했을 때는 한개 떨어진 노드와의 거리만 확인하는 것처럼 보이지만, 실제 동작을 뜯어보면 모든 노드와의 거리를 brute force 로 돌며 최단 거리를 업데이트 한다. 

 

즉, 각 단계마다 $_{N-1} P_{2}$ 개의 쌍을 단계마다 반복해서 혹인한다. $O(_{N-1} P_{2})$ 는 $O(N^2)$ 로 근사한다. 

 

※ 착각하기 쉬운 사항

 

순열이 아니고 조합 아닐까? 

A $\rightarrow$ 1 $\rightarrow$ B

B $\rightarrow$ 1 $\rightarrow$ A 

 

위는 결과 값이 동일하므로 순서를 고려하지 않아야 하는 것 아닌가? 

그렇지 않다. 

 

 

서로 방향에 따른 값이 다를 수 있다. 

 $O(N^2)$(한 노드에서 모든 노드까지의 거리) * $N$ (모든 노드) = $N^3$

 

작동 예시는 아래의 블로그를 참고하자.

https://velog.io/@ynoolee/%EB%8F%99%EB%B9%88%EB%82%98%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[동빈나]최단경로 : 플로이드 워셜 알고리즘

 

실제 구현

import sys 
import itertools
input = sys.stdin.readline
INF = 1e9

N = int(input())
E = int(input())



dist = [[INF] * (N+1) for i in range(N+1)]

for i in range(E):
    s,e,d = map(int,input().split())
    dist[s][e] = d


def floyd():
    for i in range(1, N+1):
        dist[i][i] = 0
        tmp = [p for p in range(1, N+1) if p != i]
        p_lst = list(itertools.permutations(tmp, 2))
        for s,e in p_lst:
            dist[s][e] = min(dist[s][e], dist[s][i] + dist[i][e])

floyd()

for i in dist[1:]:
    for j in i[1:]:
        print(j, end = ' ')
    print()

 

이해하고 있으니 구현이 간단하다. 

자기자신의 최단거리는 0으로 초기화 하면 되는데, 초기화를 위한 코드를 따로 작성하지 않고 상단과 같이 알고리즘을 돌 때 처리해주면 코드가 짧아진다. 

나의 경우 

from itertools import permutations

를 활용하여 본인을 제외한 순열을 만든후, 순열을 돌도록 처리했다. 

그러나 나와 같이 하지 않고 그냥 이중 for 문을 통해 처리해도 된다. permutation 특성상. 

또한 자기 자신은 어차피 최단 거리이므로 따로 처리해줄 필요 없이 for 문을 돌리면 된다. 

다만, 내가 작성한 코드가 readability 가 더 높아 보인다. 

 

개념만 이해해도 막힘없이 한번에 구현 가능하다는 점에서 굉장히 간단한 알고리즘이라고 판단된다. 

 

※ 플로이드 워셜 알고리즘을 다이나믹 프로그래밍이라고 표현한다. 

전 단계에서 최적화 했던 최단 거리를 새롭게 구하지 않고 활용한다는 점에서 다이나믹 프로그래밍의 철학을 따른다. 

이에따라 과정을 점화식으로 작성한다면 아래와 같다. 

$$D_{ab} = min(D_{ab}, D_{ak} + _{kb})$$

하지만 다이나믹 프로그래밍 철학적으로 생각안해도 워낙 간단한 개념이라 간단하게 이해 가능하다. 

 

 

실전 예제

N 개의 회사가 있다. 

회사가 서로 연결이 되어 있다면 양 방향으로 연결되어 있고 각 거리는 1 이다. 

A 는 K 번 회사를 거쳐 X 번 회사에 도달하려고 한다. 

이때 최소 거리를 구하여라. 도달할 수 없으면 -1 을 출력하라. 

• 회사의 수 NN, 경로의 개수 MM 1≤N,M≤1001≤N,M≤100
• 둘째 줄 ~ M+1M+1 줄: 연결된 두 회사의 번호 
• M+2M+2 줄: X, K 

입력 예시 

5 7 
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

 

본 문제는 다익스트라로 풀면 더 효율적이다. 

 

"""
N 개의 회사가 있다. 회사가 서로 연결이 되어 있다면 양 방향으로 연결되어 있고 각 거리는 1 이다. A 는 K 번 회사를 거쳐 X 번 회사에 도달하려고 한다.
 이때 최소 거리를 구하여라. 도달할 수 없으면 -1 을 출력하라. 
"""

import sys 
import itertools 
input = sys.stdin.readline 
INF = 1e9

N, E = map(int, input().split())

dist = [[INF] * (N+1) for i in range(N+1)]

for i in range(E):
    s,e = map(int, input().split())
    dist[s][e] = 1
    dist[e][s] = 1

X, K = map(int, input().split())


for i in range(1, N+1):
    dist[i][i] = 0
    lst = [tmp for tmp in range(1, N+1) if tmp != i]
    lst_p = itertools.permutations(lst, 2)
    for s,e in lst_p:
        dist[s][e] = min(dist[s][e] , dist[s][i] + dist[i][e])


for i in dist[1:]:
    for j in i[1:]:
        print(j, end = ' ')
    print()

ans = dist[1][K] + dist[K][4]
print(ans if ans < INF else -1)