개념
플로이드 와샬 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로를 구할 때 사용하는 알고리즘입니다. 그러나 한 지점에서 다른 특정 지점까지 최단 거리를 구하는 다익스트라 알고리즘과 달리 플로이드 와샬 알고리즘은 모든 지점에서 다른 모든 지점까지의 경로를 구하는데 사용하는 알고리즘입니다. 플로이드 와샬 알고리즘은 어떠한 지점에서 다른 지점으로 갈 때 거쳐 가는 노드를 탐색한 후 distance 리스트를 갱신하는 식으로 구현합니다. 플로이드 와샬 알고리즘의 경우 구현이 다익스트라에 비해 쉽다는 단점이 있지만 O(ElogV)의 시간 복잡도를 가지는 다익스트라 알고리즘과 달리 O(N^3)의 시간 복잡도를 가지기 때문에 사용할 수 있는 조건이 매우 한정적입니다. 따라서 문제에서 주어진 N의 범위를 잘 확인한 후 어떤 알고리즘을 사용할지 결정을 해야 합니다. 그럼 그림을 통해 알아봅시다.
먼저 이차원 리스트를 만든 후 모든 원소에 대해서 무한으로 초기화를 합니다. 그 후 자기 자신의 노드로 가는 최단 경로는 0 이기 때문에 0을 대입해 줍니다. 또한 각각의 노드에서 이동할 수 있는 노드들에 거리를 대입해 줍니다. 그러면 다음과 같은 표가 만들어 집니다.
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 4 | INF | 6 |
| 2 | 3 | 0 | 7 | INF |
| 3 | 5 | INF | 0 | 4 |
| 4 | INF | INF | 2 | 0 |
그 후 거쳐가는 노드들을 고려해 줍니다. 예를 들어 1번 노드에서 3번 노드로 가는 경우를 봅시다. 위의 표에서 해당 하는 칸은 즉 1행 3열은 INF로 초기화가 되어있습니다. 그러나 1번 노드에서 4번 노드를 거친 후 3번 노드로 가면 8 이라는 경로가 나오게 됩니다. 따라서 이런 식으로 어떠한 노드에서 다른 노드로 갈 때 거쳐가는 노드를 확인한 후 최솟값으로 대입을 해주면 다음과 같습니다.
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 4 | 8 | 6 |
| 2 | 3 | 0 | 7 | 9 |
| 3 | 5 | 9 | 0 | 4 |
| 4 | 7 | 11 | 2 | 0 |
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
INF = int(1e9)
n = 4
m = 7
graph = [[INF] * (1+n) for _ in range(1+n)]
for i in range(1, 1 + n):
for j in range(1, 1 + n):
if i == j:
graph[i][j] = 0
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
for k in range(1, 1 + n):
for a in range(1, 1 + n):
for b in range(1, 1 + n):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for i in range(1, 1 + n):
for j in range(1, 1 + n):
if graph[a][b] == INF:
print("INF", end=" ")
else:
print(graph[i][j], end=" ")
print()
|
cs |