이 글은 Graphs in Python: Dijkstra's Algorithm 에서 가져 왔음을 밝힘니다.

배경

길을 찾을 때, 여러분은 출발점으로부터 도착점까지 가장 짧은 거리가 몇 키로인지 알고 싶으실 겁니다. Dijkstra Algorithm은 그래프에서 시작 노드로부터 모든 다른 노드까지의 가장 짧은 거리를 계산하는 매우 간단하고 빠른 방법입니다.

네덜란드의 한 컴퓨터 과학자, Dijkstra가 이 알고리즘을 떠올린 것은 1956년 이었습니다. Dijkstra는 Rotterdam에서 Groningen까지 가장 짧은 거리는 얼마인지 알고 싶어했고, 간단한 알고리즘을 생각해 냅니다.

알고리즘

1. 먼저 모든 start node를 지정하고 cost 테이블을 만듭니다. cost 테이블에는 모든 노드가 리스트 되어 있고, start node로부터 cost 테이블에 있는 노드까지의 거리를 측정할 값으로 infinity가 지정이 되어 있습니다. 0번 노드가 시작 점이라면 0번 노드로부터 1번 노드와 2번 노드까지의 거리를 infinity로 지정한 것입니다.

node	cost
0	0
1	inf
2	inf

2. 현재 노드로 부터 이웃 노드를 구한뒤, 시작 노드로부터 현재노드까지의 cost와 현재 노드로부터 이웃노드로까지의 cost의 합을 구한뒤에, 시작노드로부터 현재 노드의 이웃노드까지의 cost를 비교합니다. 만일 합을 구한 값이 더 작다면 cost 테이블에서 neighbor 노드의 cost를 합한 값으로 업데이트 합니다. 그리고 현재 노드를 이웃노드로(이웃 노드중 거리가 가장 가까운 곳으로) 바꿉니다.

3. 2번 스탭을 모든 노드를 방문할 때까지 반복합니다.

예시

1. 0번 노드에서 시작하고 cost를 아래와 같이 세팅합니다.

node	cost
0	0
1	inf
2	inf

2. 0번 노드의 이웃을 구합니다. 1, 2번 노드를 구합니다.
3. 0 $\rightarrow$ 1,2 번 노드로의 cost의 합은 아래와 같이 구할 수 있습니다. 합한 값이 시작 노드로부터 1, 2번까지의 cost인 inf보다 작음으로 cost 테이블을 업데이트 시켜줍니다.

• 0-0-1 : 3km < inf
• 0-0-2 : 12km < inf

node	cost
0	0
1	3
2	12

4. 현재 노드(0)의 이웃 노드 들 중 가장 가까운 노드는 1임으로 현재 노드를 1로 옮깁니다. 그리고 시작노드로부터 현재 노드(1)까지의 거리와 현재노드와 현재 노드의 이웃노드까지의 거리를 합하고, 마찬가지로 시작노드로부터 이웃노드까지의 거리와 비교하여, 더 작다면 cost 테이블을 업데이트 합니다.

• 0-1-2 : 10km < 13km

node	cost
0	0
1	3
2	10

5. 1번 노드의 방문하지 않은 이웃노드가 2뿐이니 2를 현재 노드로 하고 알고리즘은 종료됩니다.

해설

0-2로 가는 길도 있지만 0-1-2로 가는 길이 더 짧다는 것을 알 수 있을때, 0-2로 가는 길을 선택하지 않고 0-1-2로 가는 길의 거리를 채택하는 방식입니다. 이 방식을 따르면, 그래프에서 node pair를 연결하는 가장 짧은 거리를 구할 수 있습니다.