Algorithm.Dijkstra Algorithm

[Visual Studio과 C#으로 구현/최적화문제해결]

Algorithm Dijkstra Algorithm Coding // Week07

20211022_20615034

[ Dijkstra Algorithm Coding_Theory ]

Dijkstra Algorithm은 다익스트라 알고리즘이라고 읽으며, 

최단 경로를 찾는 가장 대표적인 알고리즘이다.

주어진 출발점에서 시작, 출발점으로부터 최단거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정한다.

<알고리즘 과정>

ShortestPath(G, s) 

입력 : 가중치 그래프 G, 시작 점 s

출력 : 출발점 s로부터 n-1개의 점까지 각각 최단 거리를 저장한 배열 D

1) 배열 D의 각 요소를 무한으로 초기화시킨다. D[s]=0으로 초기화한다.

2) while(s로부터의 최단 거리가 확정되지 않은 점이 있으면) {

3) 현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의 값을 가진 점 Vmin을 선택하고, 출발점 s로부터 점 Vmin까지의 최단 거리 D[Vmin]을 확정한다.

4) s로부터 현재보다 짧은 거리로 점 Vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신한다.}

5) return D;

자료구조의 구성은 총 3개의 배열이다.

Vertex의 이름을 담는 배열 city, 최소 경로 탐색이 끝난 점을 표시하는 bool배열 sptSet,

해당 점까지의 최소 경로의 가중치를 담는 배열 D이며, 최종적으로는 D를 출력하게 된다.

<시간 복잡도>

while루프가 (n-1) 번 반복되고 1회 반복될 때, 내부에는 최소의 D[v]를 가진 점 Vmin을 찾는데 걸리는 O(n), Vmin와 연결되어, 우회할 경우 기존의 최소 가중치보다 낮은지 탐색하고 최소 가중치를 D[w]에 갱신하는데 걸리는 O(n) 이 걸린다. 따라서 O(n-1) { O(n)+O(n) } = O(n2) 이라고 할 수 있다.

​

<실행화면 01>

<실행화면 02>