1.정의
- 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘
- 최단 경로(Shortest Path)를 찾는 대표적인 기법
- 가중치가 음수인 경우 작동하지 않는다.
- 그래프 전체에서 가장 작은 가중치의 절대값만큼 모든 간선의 가중치를 더해줘서 알고리즘을 적용할 수 있다.
2.이용 사례
- 내비게이션: 지도상의 각 도시들을 정점으로, 도로들을 간선으로 갖는 그래프
- 지하철도 가능하다.
3.알고리즘
1) 출발지 정점을 제외한 모든 정점의 거리정보를 무한대로 초기화 한다.
- 노드 및 거리는 우선순위 큐에 Enqueue
2) 거리가 제일 작은 정점을 Dequeue(최초는 출발지 정점이 된다.)
3) 해당 정점과 연결된 정점들의 거리를 업데이트한다.
- 최초 거리는 무한대 이므로 무조건 업데이트가 된다.
- 시작 정점의 거리 + 가중치 = 종료 정점의 거리
- 종료 정점의 거리가 짧아지는 경우 해당 종료 정점의 직전 정점은 시작 정점으로 지정한다.(배열에 저장)
4) 위의 2 ~ 3번째 루틴을 계속 반복하여 거리를 업데이트 한다.
- 우선순위 큐가 비어질때까지 Dequeue를 하며 거리를 업데이트 한다.
5) 도착지 정점의 직전 정점을 알고있으므로(배열에 저장) 역으로 도착지 정점에서 시작 정점까지 스택에 Push를 진행한다.
6) 스택을 Pop하여 최단경로를 알 수 있다.