최단 경로 [플로이드 워셜]

최단 경로 [플로이드]

📌 플로이드 워셜 알고리즘

• 플로이드 워셜 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로구하고 싶을때 사용합니다.
• 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드는 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점이 특징입니다.
• 플로이드 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다.

특징

• D_ab = min(D_ab, D_ak + D_kb)
  • a->b로 가는 최소 비용과 (a에서 노드k로 가는 비용 + 노드K에서 b로가는 비용)이 두 값중에 최소값으로 갱신합니다.
• 자기자신으로 가는 비용은 0
• 직접 연결되어있지 않은 경로는 무한대
• 입력 데이터N이 500이하로 들어올 때만 사용가능하다. 플로이드 알고리즘은 O(N^3)의 시간복잡도로 동작하기 때문이다.

구체적인 작동 과정은 다음과 같습니다.

1. 모든 지점의 최단 경로를 구하기 위해 2중 배열로 만든다. 모든 값을 무한으로 초기화한다.
2. 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화한다.
3. A에서 B로 가는 비용은 c라고 설정하여 입력한다. 입력으로 중복된 간선이 있을 수 있다. 그래서 가장 짧은 간선 정보만 저장한다.
4. 현재 노드에서 알 수 없는 노드는 무한대가 저장되어있다.
5. 3중 반복문으로 모든 경우의 수를 순회하면서 $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$ 점화식에 따라 플로이드 워셜 알고리즘을 수행한다.

📌 플로이드 코드

• 플로이드 직접 구현
• 문제

import sys
input = sys.stdin.readline

INF = int(1e9)
N = int(input())
M = int(input())
dist = [[INF] * (N) for _ in range(N)]

for i in range(N):
    dist[i][i] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    if c < dist[a-1][b-1]:
        dist[a-1][b-1] = c

# 플로이드 워셜 알고리즘
for k in range(N):
    for a in range(N):
        for b in range(N):
            dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

print(dist)
for row in dist:
    print(' '.join([str(ele) if ele != INF else '0' for ele in row]))