1. 다익스트라 알고리즘

- 간선의 가중치가 양수인 그래프에서, 그래프 상의 한 정점에서 출발해 나머지 모든 정점으로 도달하는 최단경로를 구하는 알고리즘이다. 다음과 같은 알고리즘으로 수행된다

1) ‘시작점에서 i번 정점에 도착하는 데 걸리는 최단거리’로 dist[i] 값이 정의되는 dist 배열을 두고, i번 정점이 시작점과 인접하면 그 간선의 가중치로, 인접하지 않다면 무한대로 dist 배열을 초기화한다.

2) dist 값이 최솟값인 정점(i번 정점)을 고른 후, 시작점에서 그 정점을 거쳐 그 정점에서 인접한 정점으로 이동한다고 했을 때 거리(dist[i] + W[i][j])와 그 인접한 정점의 dist값(dist[j])을 비교한다. 만약 전자가 더 작다면, 그 인점한 정점의 dist값(dist[j])을 갱신한다.

3) 2번 단계에서 선택된 적 없는 정점들 중에서 dist 값이 최솟값인 정점을 선택하여 2번 단계를 반복한다. 더 이상 선택할 정점이 없어지면 알고리즘을 종료한다.

- 2번 단계에서 dist 값이 최솟값인 정점을 고르는 작업을 순차탐색으로 구현한다면 그 코드의 시간복잡도가 \(O(n)\)이 되고, 2번 단계를 n번 반복하게 되므로 다익스트라 알고리즘의 시간복잡도는 \(O( n^2 )\) 이다. 만약 dist 값이 최솟값인 정점을 고르는 작업을 우선순위큐를 사용하여 구현한다면 그 부분의 시간복잡도가 \(O( log V )\)가 되며 이 작업은 V회 반복하게 되고, 고른 정점과 인접한 정점의 dist값을 갱신하는 작업은 V회 동안 총 다 해 E회 반복하게 되므로, 우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 \(O( E + V log V )\) 이다.

2. 벨만포드 알고리즘

- 간선의 가중치가 실수이고 음수 간선 사이클이 없는 그래프에서, 그래프 상의 한 정점에서 출발해 나머지 모든 정점으로 도달하는 최단경로를 구하는 알고리즘이다. 다음과 같은 알고리즘으로 수행된다.

1) ‘시작점에서 i번 정점에 도착하는 데 걸리는 최단거리’로 dist[i] 값이 정의되는 dist 배열을 두고, i번 정점이 시작점과 인접하면 그 간선의 가중치로, 인접하지 않다면 무한대로 dist 배열을 초기화한다. (여기까지는 다익스트라 알고리즘과 같다.)

2) 그래프 상의 임의의 간선(i번 정점에서 j번 정점으로 이동하는 간선)을 하나 고른 후, 시작점에서 i번 정점을 거쳐 j번 정점으로 이동한다고 했을 때 거리(dist[i] + W[i][j])와 j번 정점의 dist값(dist[j])을 비교한다. 만약 전자가 더 작다면, j번 정점의 dist값(dist[j])을 갱신한다.

3) 모든 간선에 대해 2번 단계를 수행하고, 이를 다시 V번 반복 후 알고리즘을 종료한다.

- 모든 간선에 대해 2번 단계를 수행하는 시간복잡도가 O(E)이고, 이를 다시 V번 반복하므로 벨만포드 알고리즘의 시간복잡도는 O(VE)이다.

- 갱신되는 dist[j]의 관점에서 보면, 벨만포드 알고리즘은 dist[j]의 값을 선행되는 연산의 결과값으로 얻은 dist 값을 이용한 연산식의 최솟값으로 구하므로 벨만포드 알고리즘을 다이나믹 프로그래밍의 일종으로 볼 수 있다. 점화식 dist[j] = min(dist[i] + W[i][j])을 쓰고 dist[i]를 구하는 과정을 재귀호출로 구현할 수도 있다.