플로이드 와샬 알고리즘

플로이드 와샬 알고리즘

그래프 자료구조에서, 모든 노드에 대해 다른 노드로의 최단 경로를 구하는 알고리즘. 다이나믹 프로그래밍의 일종이다.

방법?

다음과 같은 그래프가 있다고 가정하자.

각 노드에 대해 다른 노드로의 직선 비용은 다음과 같다.

from	to 1	to 2	to 3	to 4
1	0	5	8	∞
2	6	0	∞	9
3	∞	∞	0	3
4	2	∞	4	0

다른 노드를 거치지 않고 바로 목적지 노드로 가기 위해서는 위 표의 비용이 소비된다. 이제 모든 노드에 대해 최소 비용 경로를 알기 위해 표를 갱신해야 한다. 비교 기준은 다음과 같다.
노드1에서 노드2로 가는 현재 최소 비용 VS 노드1에서 노드3으로 가는 비용 + 노드3에서 노드2로 가는 비용

• 노드 1을 거쳐가는 경우
  노드 1을 거쳐서 다른 노드로 가는 경우가 더 빠르다면 해당 경우로 최소 비용을 교체한다.
  그 결과는 다음과 같다.

from	to 1	to 2	to 3	to 4
1	0	5	8	∞
2	6	0	14	9
3	∞	∞	0	3
4	2	7	4	0

• 노드 2를 거쳐가는 경우
  노드 1을 거쳐가는 경우를 계산한 결과 표에서, 노드 2를 거쳐가는 경우로 동일한 작업을 수행한다.
  그 결과는 다음과 같다.

from	to 1	to 2	to 3	to 4
1	0	5	8	14
2	6	0	14	9
3	∞	∞	0	3
4	2	7	4	0

• 노드 3를 거쳐가는 경우
  노드 1과 2를 거쳐가는 경우를 계산한 결과 표에서, 노드 3을 거쳐가는 경우로 동일한 작업을 수행한다.
  그 결과는 다음과 같다.

from	to 1	to 2	to 3	to 4
1	0	5	8	11
2	6	0	14	9
3	∞	∞	0	3
4	2	7	4	0

• 노드 4를 거쳐가는 경우
  마지막으로 노드 4를 거쳐가는 경우를 계산한다. 그 결과는 다음과 같다.

from	to 1	to 2	to 3	to 4
1	0	5	8	11
2	6	0	13	9
3	5	10	0	3
4	2	7	4	0

추천 문제

프로그래머스 - 순위