다익스트라 알고리즘(Dijkstra Algorithm)이란?

다익스트라 알고리즘(Dijkstra Algorithm)은 그래프 내 하나의 정점에서 다른 모든 정점까지의 최단 거리/경로를 구하는 

알고리즘이다. BFS와 다른 점은 가중치 그래프에서도 사용 가능하다는 것이다. 다만, 그래프 내 엣지들은 모두 양수여야 한다.

다익스트라 알고리즘의 기본 동작 원리는 다음과 같다.

1. 출발 정점을 설정한다.
2. 최단 거리 테이블을 초기화한다. 이때, 초기 값은 출발 정점을 제외하고 모두 무한대 값을 가진다.
3. 출발 정점과 연결된 정점 가운데 방문하지 않는 정점들을 찾는다.
4. 그중 최단 거리가 가장 짧은 정점을선택한다.
    이때, 최단 거리란 갱신하기 전 최단 거리를 의미하며 2번에서 초기화한 테이블의 값과는 다르다.
5. 해당 정점을 거쳐 다른 정점으로 가는 거리를 계산한다.
    그리고 그 값을 갱신하기 전 최단 거리와 비교하여 더 짧은 거리로 최단 거리 테이블을 갱신한다.
6. 위의 과정을 반복한다.

 

출발 정점을 1로 설정 한다.

정점		1	2	3	4	5	6
최단 거리		0	2	3	6	INF	INF

 

2번, 3번, 4번 정점의 최단 거리를 갱신한다.

 

 

최단 거리가 가장 짧은 2번 정점을 선택한다.

정점		1	2	3	4	5	6
최단 거리		0	2	3	6	INF	6

 

6번 정점의 최단 거리를 갱신한다.

 

 

그 다음으로 짧은 3번 정점을 선택한다.

정점		1	2	3	4	5	6
최단 거리		0	2	3	4	INF	6

 

4번 정점의 최단 거리를 갱신한다.

 

 

그 다음으로 짧은 4번 정점을 선택한다.

정점		1	2	3	4	5	6
최단 거리		0	2	3	4	INF	6

 

4번 정점과 연결된 정점 중 갱신할 경로는 없다.

 

 

그 다음으로 짧은 6번 정점을 선택한다.

정점		1	2	3	4	5	6
경로		0	2	3	4	INF	6

 

6번 정점과 연결된 정점 중 갱신할 경로는 없다.

 

 

1번과 연결된 모든 정점을 방문하였다.

정점		1	2	3	4	5	6
최단 거리		0	2	3	4	INF	6

 

최종 완료된 최단 거리 테이블