다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path)탐색 알고리즘이다.
흔히 최소비용으로 선로 또는 파이크 네트워크, 인공위성 GPS 소프트웨어에서 가장 많이 사용된다.
다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 이 떄 음의 간선을 포함할 수 없는데 현실 세계엔 음의 간선이 존재하지 않기 때문에 현실 세계에 사용하기 매우 좋은 알고리즘이라고 한다.
다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러개의 최단 거리로 이루어져 있기 떄문이다.
하나의 최단거리를 구할 때 직전까지 구했던 최단거리를 이용한다.
1. 출발 노드를 정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐서 특정 노드로 가는 비용을 고려해 최소 비용을 갱신한다.
5. 3번~4번 과정을 반복한다.
1번노드를 선택하여 최단경로를 구해본다.
최단경로의 경우 배열의 형태로 값이 저장되게 된다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 2 | 4 | inf | inf |
선택이 이루어지면 최단경로가 확정된다.
다음으로 가장 적은 가중치는 2번노드이다. 2번노드를 선택해주고, 2번노드를 거쳐서 특정 노드로 가는 최소 비용을 갱신한다.
또한 선택 된 노드는 더이상 비용을 확인하지 않아도 된다.
2번 노드를 선택했으니 2번 노드와 인접한 노드들을 2번노드를 거쳐서 갈경우 거리가 줄어드는지 비교해본다.
4번노드를 2번노드를 통해 가더라도 4라는 값이 나오므로 변경되는 것은 없다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 2 | 4 | inf | inf |
다음으로 적은 가중치인 3번노드를 선택한다.
3번노드와 인접해있는 노드는 1, 3, 4, 5번 노드이다 1번은 이미 선택 되었다.
이미 선택된 노드는 비용을 갱신하지 않아도 되므로 4, 5번 노드만 확인하면 된다
3번노드를 통해 4번노드로 갈경우 7이다. 기존의 4보다 크기 떄문에 갱신하지 않는다.
5는 inf지만 3번노드를 통해 갈 경우
1번 노드에서 3번노드까지 2
3번노드에서 5번노드까지 1
2 + 1 = 3 < inf
기존의 값보다 더 작으므로 갱신해준다.
그후로 더 작은 값인 5번노드를 선택해준다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 2 | 4 | 3 | inf |
5번 노드에 인접해있는 노드는 3, 4, 6노드이다. 3은 이미 선택되었으니 4, 5노드를 확인한다.
6번노드는 5번노드를 통해서 갈 경우 거리가 4가된다. inf보다 작으니 갱신해준다. 4번노드는 갱신될 필요가 없다.
| 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 2 | 4 | 3 | 4 |
이런 식으로 최소 비용 구하는 알고리즘인 다익스트라 알고리즘이 진행된다.
시간복잡도
log(n log n)