[알고리즘] 최단 경로 : 모든 지점에서 다른 모든 지점까지의 최단 경로 / 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) / 파이썬

최단 경로 (Shortest Path)

• 가장 짧은 경로를 찾는 알고리즘
• '길 찾기' 문제라고도 불린다.
• 보통 그래프를 이용해 표현한다.

 

다익스트라 알고리즘 vs 플로이드 워셜 알고리즘

---

다익스트라 알고리즘

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용한다.
• 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다.  그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신한다.
• 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트를 이용한다.
• 다익스트라 알고리즘은 그리디 알고리즘이다.

 

2021.07.27 - [파이썬 Python] - [알고리즘] 최단 경로 : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 / 다익스트라(Dijkstra) 알고리즘/ 개선된 다익스트라 알고리즘 / 파이썬

[알고리즘] 최단 경로 : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 / 다익스트라

 

 

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용한다.
• 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라와는 다르다.
• 2차원 리스트에 최단 거리 정보를 저장한다.
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이다.

 

원리

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

예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다.

즉, A → 1번 노드 → B 로 가는 비용을 확인한 후, 현재 최단 거리 테이블에 저장된 A → B 로 가는 비용보다 작으면 최단 거리를 갱신한다.

 

알고리즘

1. 현재 확인하고 있는 노드를 제외하고, 나머지 N - 1 개의 노드 중에서 서로 다른 노드 (A, B)쌍을 선택한다. 
2. A → 1번 노드 → B 로 가는 비용을 확인한 후 최단 거리를 갱신한다.
3. P(N-1, 2)개의 쌍을 단계마다 반복해서 확인한다.

 

점화식

Dab = min(Dab, Dak + Dkb)

Dab : A에서 B로 가는 최소 비용

Dak : A에서 K로 가는 비용

Dkb : K에서 B로 가는 비용

Dak + Dkb : A에서 K를 거쳐 B로 가는 비용

min(Dab, Dak + Dkb) : A에서 B로 바로 가는 거리와 A에서 K를 거쳐 B로 가는 거리 중 더 짧은 것을 선택

 

 

예시

step 0

연결된 간선은 그 값을 담고, 연결되지 않은 간선은 무한 값을 담는다.

예를 들어 1번 노드에서 4번 노드로 가는 비용은 6이기 때문에 2차원 리스트의 1번째 행 4번째 열의 값이 6이 된다.

자기 자신에서 자기 자신으로 가는 비용은 0이기 때문에 Dii(1≤i≤N)값은 모두 0으로 초기화한다.

Dii : i에서 i로 가는 비용, 즉 자기 자신에서 자기 자신으로 가는 비용
2차원 리스트에서는 대각선 값에 해당한다.

출발\ 도착	1번	2번	3번	4번
1번	0	4	무한	6
2번	3	0	7	무한
3번	5	무한	0	4
4번	무한	무한	2	0

 

step 1

1번 노드를 거쳐 가는 경우를 고려해보자.

총 4개의 노드 중, 현재 확인하고 있는 1번 노드를 제외하고 3개의 노드 중에서 서로 다른 노드 2개를 선택해야 한다.

P(3, 2) = 3P2 = 3! / (3-2)! = 6 가지 경우가 존재한다.

D23 = min(D23, D21 + D13)

D24 = min(D24, D21 + D14)

D32 = min(D32, D31 + D12)

D34 = min(D34, D31 + D14)

D42 = min(D42, D41 + D12)

D43 = min(D43, D41 + D13)

첫 번째와 두 번째 식만 계산해보자.

• D23 = 현재 테이블에 저장되어있는 2번 노드에서 3번 노드로 가는 비용 = 7
• D21 + D13 = 2번 노드에서 1번 노드로 가는 비용 + 1번 노드에서 3번 노드로 가는 비용 = 3 + 무한

1번 노드를 거치지 않는 경로가 더 짧으므로, 테이블을 갱신하지 않는다.

 

• D24 = 2번 노드에서 3번 노드로 가는 비용 = 무한
• D21 + D14 = 2번 노드에서 1번 노드로 가는 비용 + 1번 노드에서 4번 노드로 가는 비용 = 3 + 6 = 9

1번 노드를 거치는 경로가 더 짧으므로, 테이블을 갱신한다.

 

 

6가지 식을 모두 계산해서 값을 갱신하면 테이블이 다음과 같이 바뀐다.

출발\ 도착	1번	2번	3번	4번
1번	0	4	무한	6
2번	3	0	7	9
3번	5	9	0	4
4번	무한	무한	2	0

 

step 2

2번 노드를 거쳐 가는 경우를 고려해보자.

D13 = min(D13, D12 + D23)

D14 = min(D14, D12 + D24)

D31 = min(D31, D32 + D21)

D34 = min(D34, D32 + D24)

D41 = min(D41, D42 + D21)

D43 = min(D43, D42 + D23)

갱신 결과

출발\ 도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	무한	무한	2	0

 

step 3

3번 노드를 거쳐 가는 경우를 고려해보자.

D12 = min(D12, D13 + D32)

D14 = min(D14, D13 + D34)

D21 = min(D21, D23 + D31)

D24 = min(D24, D23 + D34)

D41 = min(D41, D43 + D31)

D42 = min(D42, D43 + D32)

갱신 결과

출발\ 도착	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

step 4

4번 노드를 거쳐 가는 경우를 고려해보자.

D12 = min(D12, D14 + D42)

D13 = min(D13, D14 + D43)

D21 = min(D21, D24 + D41)

D23 = min(D23, D24 + D43)

D31 = min(D31, D34 + D41)

D32 = min(D32, D34 + D42)

갱신 결과

출발\ 도착	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

최종 결과

노드의 개수가 4개 이므로 총 step 4까지의 알고리즘을 수행하였다.

step4의 갱신 결과인 최종 테이블에 기록되어 있는 내용이 모든 노드에서 모든 노드로 가는 최단 거리 정보를 담고 있는 것이다.

 

 

소스 코드

INF = int(1e9)

N = int(input())
M = int(input())
# 2차원 리스트(그래프)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (N+1) for _ in range(N+1)]

# 자기자신으로 가는 비용은 0으로 초기화
for a in range(1, N+1):
    for b in range(1, N+1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보
for _ in range(M):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, N+1):
    for a in range(1, N+1):
        for b in range(1, N+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, N+1):
    for b in range(1, N+1):
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b], end=' ')
    print()

입력

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

출력

0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0

 

시간 복잡도 : O(N^3)

2차원 리스트를 처리해야 하므로 N번의 단계에서 매번 O(N^2)의 시간이 소요된다.

혹은 3중 for문이기 때문에 O(N^3)이라고 생각해도 된다.

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년