다익스트라 알고리즘
하나의 정점에서 출발했을 때 다른 모든 정점으로의 최던 경로를 구하는 알고리즘.
가장 적은 비용을 하나씩 선택을 해서 그 노드의 인접한 노드로 가는 길을 하나씩 계산해서 푼다.
1에서 3으로 가는 비용이 바로가는것보다 2을 거쳐간다면 거쳐가는 만큼의 비용으로 1에서 3으로 가는 비용을 수정한다.
플로이드 와샬 알고리즘
모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘
거쳐가는 정점을 기준으로 한다. 아예 반복문의 중심에 거쳐가는 노드가 있다.
에초에 거쳐가는 노드를 하나씩 설정해서 확인한다.
그래프가 있을 경우 2차원 배열의 형태로 유지한다.
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 무한 | 무한 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 무한 | 0 | 4 |
| 4번 | 무한 | 무한 | 3 | 0 |
왼쪽 번호에서 상단 번호로 가는 숫자를 적게된다.
각각에 노드에서 각각의 노드로 가는 비용을 적게된다.
이 테이블이 의미하는 바는 현재까지 계산된 최소 비용이다. 이 이차원 배열을 반복하여 갱신하며 모든 최소 비용을 구한다.
그 반복의 기준이 거쳐가는 정점이다.
노드 1을 거쳐가는 경우
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 무한 | 무한 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 무한 | 0 | 4 |
| 4번 | 무한 | 무한 | 3 | 0 |
노드 1을 거쳐가는 경우 이곳을 갱신해 주면 된다.
그림을 보지 않아도 된다. 표만 보고도 갱신 할 수 있다.
기존의 거리 vs 1을 거쳐서 가는 거리 이렇게 비교를 해주면 된다.
3에서 2로가는 경우 1을 거쳐서 가게되면
기존의 거리 3 to 1 + 1 to 2
무한 vs ( 2 + 7 )
두 값중 더 작은 값으로 교체가 된다. 무한보다 9가 더 작기 때문에 9로 교체가 된다.
반면 2에서 3으로 가는 경우는 기존(9) vs 1을거쳐(5 + 무한) 이기 때문에 교체가 일어나지 않는다.
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 무한 | 무한 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 무한 | 무한 | 3 | 0 |
노드 2를 거쳐가는경우
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 무한 | 무한 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 무한 | 무한 | 3 | 0 |
이렇게 6개를 비교해 주면 된다.
예) 1에서 3번 가는 경우
기존 1to2 + 2to3
무한 vs 7 + 9
7+9=16
그럼 이런 결과가 나온다.
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 16 | 13 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 무한 | 무한 | 3 | 0 |
노드 3을 거쳐가는 경우
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 16 | 13 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 무한 | 11 | 3 | 0 |
이렇게 6개를 비교해준다.
4에서 2로갈 경우
기존 vs 4to3 + 3to2
무한 vs 3 + 9 = 11
결과)
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 16 | 13 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 5 | 11 | 3 | 0 |
노드 4를 거쳐가는 경우
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 16 | 13 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 5 | 11 | 3 | 0 |
마지막 결과)
| 1번 | 2번 | 3번 | 4번 | |
| 1번 | 0 | 7 | 16 | 13 |
| 2번 | 5 | 0 | 9 | 6 |
| 3번 | 2 | 9 | 0 | 4 |
| 4번 | 5 | 11 | 3 | 0 |
시간복잡도
O(n^3)