[c++] 알고리즘 개념공부 :: 최단경로 찾기 (Dijkstra 알고리즘)

최단 경로

 그래프에서 유도되는 문제들 중 최단 경로 문제가 있다. 주어진 그래프에서 특정 정점에서 다른 정점까지의 최단 경로(가중치 합이 최소인 경로)가 무엇인지를 알아내는 문제이다.

 이는 이전의 MST 문제와 다르다. 모든 정점을 포함할 필요가 없기 때문이다.

 

하지만 MST에서 사용했던 Prim(Dijkstra) 알고리즘을 응용해서 구현할 수 있다.

[MST]

 

Dijkstra 알고리즘

구현

vertice(정점)는 3가지 분류로 나뉜다.

• tree vertice(T) : tree에 속해 있는 정점
• fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점
• unseen vertice (U) : 나머지

 MST에서 T와 F의 정점 사이의 최소 가중치를 계속 갱신해주었던 것 대신에, 최단 경로 알고리즘에서는 시작 정점부터 F의 정점까지 경로를 갱신해준다.

 F의 특정 정점 V를 보았을 때, T-F의 간선을 따라 시작정점부터 V까지의 경로의 최소값이 현재 저장되어있다고 하자. 이 때, 다른 정점 V'가 tree에 포함되면 V'-V 간선의 포함으로 이 간선을 통한 경로가 기존에 존재하던 경로보다 짧아질 수 있다. 따라서 이를 갱신해주는 것이다.

 

 위의 예제에서 Tree set에 시작 정점인 A밖에 없었을 때, D까지의 경로는 A-D 간선을 따라 가중치가 3이다. 하지만 이후 C가 Tree set에 포함되면 D까지의 경로는 A에서 C, C에서 D를 거치는 1+1 = 2의 가중치를 가지는 경로가 최소가 된다.