[알고리즘] 다익스트라(Dijkstra)

[개념]

 

다익스트라 알고리즘이란 하나의 정점에서부터 다른 정점들까지의 최단거리를 구하는데 사용되는 탐색 알고리즘이다.
정점까지의 최단 경로를 구할 때 , 이전에 구한 다른 정점들까지의 최단 경로를 구한다.

 

1. 출발 정점을 구한다

2. 출발 정점과 인접한 점들을 방문 처리한다.

3. 출발 정점과 인접한 점들 중에서 비용이 가장 적은 정점으로 간다.

4. 다음 정점에서 마찬가지로 2,3번을 반복한다.

 

위의 과정을 반복할 때 한번 방문했던 정점은 재방문 하지않는다. 3번의 과정을 통해 최단 경로를 보장할 수 있다. 현재 정점을 기준으로 비용이 가장 적은 정점으로 가므로 이것이 최단 경로가 되는 것이다. 

 

 

위의 그래프를 기준으로 각 정점들의 거리를 배열에 초기화하면 다음과 같이 된다. 

	1	2	3	4	5	6
1	0	3	4	2	INF	INF
2	3	0	INF	INF	4	5
3	4	INF	0	4	INF	INF
4	2	INF	INF	0	1	INF
5	INF	4	4	1	0	1
6	INF	5	INF	INF	1	0

1. 출발 정점을 1번으로 한다면 

출발 정점으로부터 각 정점까지의 최단 거리를 다음과 같이 초기화 할 수 있다.

1	2	3	4	5	6
0	INF	INF	INF	INF	INF

2.출발 정점과 인접한 점인 2,3,4의 거리를 update 해주고 인접한 점 중에서 가장 비용이 적은 4번 정점이 다음 방문할 정점이 된다.

1	2	3	4	5	6
0	3	4	2	INF	INF

 

3. 다음으로 4번 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점은 5번이 되므로 5번까지의 거리를 update 해주고 5번도 다음 방문 정점 리스트에 추가해준다.

1	2	3	4	5	6
0	3	4	2	3	INF

이 때 다음 방문 정점 리스트에서 이전 정점부터 해당 정점까지의 거리 중 가장 짧은 것은 (2번 정점 , 거리 : 3), (3번 정점 , 거리 4),(5번 정점, 거리 1)이므로 거리가 가장 짧은 5번 정점이 다음 방문 정점이 된다.

1	2	3	4	5	6
0	3	4	2	3	INF

5번 정점과 인접한 정점 중에서 아직 방문하지 않은 6번 정점까지의 거리도 6(2+1+1)으로 업데이트 해주고 다음 방문 정점 리스트에 추가해준다. 마찬가지로 다음 방문 정점 리스트에서 거리가 가장 짧은 6번 정점 ( 거리 : 1)이 다음 방문 정점이 된다 .

 

6번 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점은 존재하지 않으므로 정점 방문 리스트는 업데이트 해주지 않는다.

정점 방문 리스트에 남은 정점들 (2번 정점 , 거리 : 3), (3번 정점 , 거리 4) 중에서 가장 거리가 짧은 정점은 2번 정점이 되므로 다음 방문 정점은 2번이 된다.

 

마찬가지로 2번과 인접한 정점 중에서 아직 방문하지 않은 정점은 없으므로 정점 방문 리스트를 업데이트 해주지 않고 마지막으로 남은 3번 정점을 방문한다. 3번 또한  인접한 정점 중에서 아직 방문하지 않은 정점은 없으므로 정점 방문 리스트는 이제 비어있으므로 끝나게 된다.

 

이와 같이 1번 정점에서부터 각 정점들 까지의 최단거리를 다익스트라 알고리즘을 사용해 구할 수 있다.

 

 

 

최단 경로를 구하는 알고리즘으로는 다익스트라, 벨만포드, 플로이드 워샬 등이 있다.

벨만포드는 음수의 간선이 존재할 때 사용하면 유리하고 플로이드 워샬의 경우 모든 정점들간의 최단거리를 구하는 알고리즘이다.

따라서 하나의 정점에서 다른 정점들까지의 최단거리를 구하고 양수의 간선들로만 이루어진 경우라면 다익스트라 알고리즘을 사용해 최단경로를 구한다.

 

[코드]

 

[같이 풀어보면 좋은 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스