데이크스트라의 알고리즘

1959년 에드거 데이크스트라가 최단 경로 문제를 푸는 굉장히 흥미로운 알고리즘을 만들었다.

 

1. 시작 정점을 현재 정점으로 한다.

2. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다.

3. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다.

4. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다.

 

 

 

0에 갈 수 있는 정점은 4, 1, 5 이다. 이들의 최단 거리를 저장한다.

이어 가장 가까운 최단거리인 4를 다음 정점으로 한다.

4에서 갈 수 있는 6, 1, 3의 최단 거리를 0에서 시작하는 거리값으로 저장한다.

예를 들어 6인 경우는 3+5이니 8이다. 그러므로 8을 저장한다.

여기서 원래 1까지 가는 거리가 7이였으나 4를 거쳐 1로 가는 (3+2) 가 더 최단거리므로 업데이트한다.

이어 가장 가까운 최단거리인 1을 다음 정점으로 한다.

 

1에서 갈 수 있는 정점은 3, 2, 5 이다.

마찬가지로 최단거리면 업데이트 하고, 없으면 채운다.

이어 가장 가까운 최단거리인 6을 다음 정점으로 한다.

이를 끝까지 반복해준다.

 

데이크스트라의 알고리즘은 매핑과 GPS 기술에도 동일한 방식을 사용할 수 있다. 각 간선의 가중치를 가격이 아닌 도시에서 다른 도시로 운전할 때 얼마나 빨리 갈 수 있느냐로 표현한다면 쉽게 데이크스트라의 알고리즘을 사용해 한 장소에서 다른 장소로 운전할 할때 어떤 경로로 가야할 지 결정할 수 있다.