가장 빠르게 도달하는 방법

다익스트라는 최단 경로 알고리즘중 하나로 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다.

알고리즘

다익스트라는 5단계로 나타낼 수 있습니다.

• 출발 노드를 설정한다.
• 최단 거리 테이블을 초기화한다.
• 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
• 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
• 위 과정에서 3 ~ 4를 반복한다.

주변에서 다익스트라

다익스트라 알고리즘은 음의 간선이 없을 때 정상적으로 작동합니다. 현실에서 길은 음수로 표현할 수 없기 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 합니다.

구현 방법

간단한 다익스트라 알고리즘

순차탐색을 활용한 다익스트라

개선된 다익스트라 알고리즘

최소 힙을 활용한 다익스트라