[알고리즘] 최단경로 알고리즘 - Floyd 알고리즘

앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제가 여러가지 방법이 있다고 했다.

1. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem
2. 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)
3. 하나의 목적지로 가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)
4. 마지막으로 모든 최단 경로를 구하는 문제(all pairs shortest path problem)

플로이드-워셜 알고리즘은 이중에서 마지막, 모든 최단 경로를 구하는 방법이다.
(다익스트라는 single source shortest path problem 였다.)
또한 다익스트라 알고리즘은 음의 가중치를 가진 간선은 못쓴다는 제약이 있었다.
하지만 플로이드-워셜에선 사용이 가능하다.

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는는 2차원 배열이 된다.
플로이드-워셜은 optimal substructure의 개념을 이용하여 최단 경로를 찾는다.
optimal substructure이란 특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.

플로이드-워셜 알고리즘의 기본 로직

플로이드-워셜에선 2개의 테이블을 사용하는데, 하나는 모든 경로에 대한 비용을 저장하는 테이블, 나머지 하나는 각 정점까지 가기 직전의 정점을 저장한 테이블이다. 각각의 테이블을 D와 P라고 하자.
테이블 D와 P에는 처음엔 인접리스트에 대한 내용만 들어가게 된다.
그 후 경로를 추가 할 때마다 두 테이블이 갱신된다.

위 그래프를 보자. 플로이드-워셜에선 처음엔 인접리스트의 정보만 들어간다고 했다.
따라서 맨 처음에 초기화되는 테이블 D,P는 다음과 같다

거리를 저장한 테이블 D

	1	2	3	4	5
1	0	3	8	INF	-4
2	INF	0	INF	1	7
3	INF	4	0	INF	INF
4	2	INF	-5	0	INF
5	INF	INF	INF	6	0

직전 정점을 저장한 테이블 P

	1	2	3	4	5
1	NIL	1	1	NIL	1
2	NIL	NIL	NIL	2	2
3	NIL	3	NIL	NIL	NIL
4	4	NIL	4	NIL	NIL
5	NIL	NIL	NIL	5	NIL

여기서 INF는 무한대를 뜻하며, NIL 은 직전 정점이 없다(즉 연결되어 있지 않다)는 뜻이다. 위 정점은 아무런 정점을 중간 경로로 사용하지 않고, 오직 인접 리스트로만 표현한 것이기 떄문에, 그 외는 INF,NUL로 명시되었다.

이제 여기서 경로 1을 중간 경로로 하는 테이블을 구해보자. 얼핏 봐도 4->2가 중간경로 1을 추가하면 4->1->2로 접근할 수 있고, 4->5도 4->1->5로 접근할 수 있게 됨을 볼 수 있다.

중간 경로 1을 추가한 테이블 D

	1	2	3	4	5
1	0	3	8	INF	-4
2	INF	0	INF	1	7
3	INF	4	0	INF	INF
4	2	5	-5	0	-2
5	INF	INF	INF	6	0

중간 경로 1을 추가한 테이블 P

	1	2	3	4	5
1	NIL	1	1	NIL	1
2	NIL	NIL	NIL	2	2
3	NIL	3	NIL	NIL	NIL
4	4	1	4	NIL	1
5	NIL	NIL	NIL	5	NIL

이렇게 경로가 갱신되며, 갱신 될 시 테이블 P의 해당 컬럼 또한 1로 갱신된다.
직전 경로가 갱신되므로 테이블 P를 이용하면 최단 경로 또한 구할 ㅅ ㅜ있다.
따라서 다음과 같은 관계가 성립됨을 알 수 있다.

C++ 플로이드-워셜 알고리즘 코드