[Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘

https://growth-coder.tistory.com/41

[Algorithm] 다익스트라 (Dijkstra algorithm), 벨만 포드(Bellman ford algorithm)

다익스트라,  벨만 포드에 이어서 플로이드 와샬 알고리즘도 알아보려고 한다.

 

다익스트라와 벨만 포드의 공통점은 두 알고리즘 모두 정점 하나에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이라는 점이다.

 

두 알고리즘의 차이는 음의 간선의 허용 여부이다.

 

플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다.

 

이 알고리즘의 핵심은 중간 정점이다.

 

a에서 b로 가는 최단 거리를 구할 때 중간 노드인 k를 사용하는 것이다.

 

u -> v와 u -> k -> v 중 최단 거리를 계속 갱신해가는 알고리즘이다.

 

진행 과정은 다음과 같다.

 

2차원 배열을 만든다. arr[u][v]의 의미는 정점 u에서 v로 가는 최단 거리를 의미한다.

 

1. 2차원 배열의 값을 모두 무한대로 초기화한다.

	a	b	c
a	INF	INF	INF
b	INF	INF	INF
c	INF	INF	INF

2. arr[ i ][ i ]의 값을 0으로 설정한다. 시작 지점과 도착 지점이 같을 때의 최단 거리는 0이기 때문이다.

	a	b	c
a	0	INF	INF
b	INF	0	INF
c	INF	INF	0

3. 그래프의 간선을 보고 간선의 비용을 기록한다.

	a	b	c
a	0	10	6
b	INF	0	2
c	INF	4	0

4. 지금부터 모든 점에 대해서 해당 점을 경유하는 경로의 최단 거리를 갱신한다.

코드로 보는 편이 이해가 빠를 것이다.

 

정점의 개수 n과 간선의 개수 m을 입력받고 모든 값을 무한대로 초기화 한다.

import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
MAX=1e9
cost=[
    [MAX]*(n+1)
    for _ in range(n+1)
]

 

시작점과 도착점이 동일한 곳은 0으로 초기화 하고 간선의 정보를 입력받아 비용을 입력한다.

for i in range(1, n+1):
    cost[i][i]=0
for _ in range(m):
    u, v, w = map(int, input().split())
    cost[u][v]=w

 

삼중 반복문을 통해 특정 노드를 경유할 때의 최단 거리를 갱신한다.

for k in range(1, n+1):
    for u in range(1, n+1):
        for v in range(1, n+1):
            cost[u][v]=min(cost[u][v], cost[u][k]+cost[k][v])