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

Dijkstra Algorithm?

쉽게 말해서 특정 지점에서 다음 지점까지 갈 수 있는 최단 경로를 탐색하는 알고리즘이다. 현실에서는 GPS를 통해서 경로탐색을 하거나 소셜네트워크 분석을 할 때 많이 사용되고 있다. 다익스트라 알고리즘으로 경로 탐색을 할 때는 여러 개의 최단거리 중에서 또 그 다음 최단 거리들을 분석하기 때문에 하나의 큰 문제를 쪼개서 해결하는 '동적계획법'(Dynamic Programing)이라 할 수 있다. 

 

# 예시 그래프  A에서 B로 가는 최소값은?

 

최단거리에서 경우의 수를 구하자!

위와 같이 그래프가 있다고 생각해보자. A에서 출발한다고 할 때, 방문할 수 있는 곳은 F, G, H가 있다. 그럼 갈 수 있는 곳에 대한 비용을 표로 정리하면 다음과 같다. 방문할 수 없는 곳에 대해서는 무한이라고 가정하자. 이 다음에는 최단거리의 F로 가서 F에서 갈 수 있는 곳에 대해서 비용을 계산한다. 이때 비용이 이전보다 적게 든다면 값을 업데이트를 해준다.  그러면 G로 가는 비용이 15에서 10으로 줄어든 것을 확인할 수 있다. 

F	G	H	B
9	10	11	-

이후 G에서 방문하지 않은 곳에 대해서 다시 비용계산을 실행하면 H까지는 12, B까지는 14가 나온다. H까지 가는 비용은 오히려 기존의 11이 더 낮은 비용이기 때문에 업데이트는 발생하지 않고, B의 14값만 새롭게 업데이트가 된다.

F	G	H	B
9	10	11	14

B에서도 방문하지 않은 H에 대해서 비용계산을 할 수 있지만 20이나 비용이 들기 때문에 탐색은 여기서 멈추게 된다. 그럼 우리는 최종적으로 A에서 B를 가기 위한 최소 비용이 14인 것을 알 수 있다. 

 

방문하지 않은 곳에 대한 비용을 계산하면서 최단거리를 찾으면 된다!