[파이썬] 플로이드 워셜

# 플로이드 워셜
INF = float('inf')
n = 4
nodes = [[1, 2, 4], [1, 4, 6], [2, 1, 3],
	[2, 3, 7], [3, 1, 5], [3, 4, 4], [4, 3, 2]]
graph = [[INF] * (n+1) for _ in range(n+1)]
for u, v, w in nodes:
    graph[u][v] = w
for k in range(1, n+1):
    graph[k][k] = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in graph[1:]:
    print(i[1:])

---

플로이드 워셜 알고리즘은 2차원 리스트를 통한 인접 행렬 방식을 사용하고, 다익스트라의 경우 1차원 리스트를 통한 인접 리스트 방식을 사용한다.

1번, 2번, 3번, 4번 총 4개의 노드가 존재한다.

만약 k가 2일 경우, 2번 노드를 거쳐 지나가는 모든 경우를 찾는다.

2번 노드를 제외한 1번, 3번, 4번 세 개의 노드에서 두 개의 노드를 선택해야한다.

3P2를 통해 (1, 3), (1, 4), (3, 1), (3, 4), (4, 1), (4, 3) 총 6개의 경우를 찾아낸다.

조합이 아닌 순열이 사용되는 이유는 양 노드간의 가중치가 서로 다르기 때문이다.

    # k = 2 가정
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == k or j == k or i == j:
                continue
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

이 부분이 2중 for문 n^2 탐색을 통해, 가능한 n-1P2 가지의 경우의 수를 찾는 코드이다.

if문을 추가하면 총 16번의 탐색 중 10번은 continue 가 실행될 것이다.