[파이썬] [최단경로] 개념 정리 2

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘
• 다이나믹 프로그래밍
• 2차원 리스트에 최단 거리 정보를 저장한다.

구현

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

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

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

for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a][b] = cost

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            # a에서 b로 가는 비용과 a에서 k를 거쳐 b로 가는 비용을 비교
            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("INF", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

Input

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

Output

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