다익스트라 최단경로 알고리즘
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로를 계산
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복(그리디)
- 다익스트라 최단경로 알고리즘
- 출발 노드를 결정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 3번과 4번을 반복