가장 짧은 경로를 찾는 알고리즘 일명 길찾기 문제

다익스트라 알고리즘

• 한 노드에서 모든 다른 노드로의 최단 거리를 구함 (One To All)
• 음의 간선이 없을 때 동작 가능

→ 음의 간선이 없는 현실 세계의 GPS 소프트웨어 기본 알고리즘

• 그리디 알고리즘으로 분류 (가장 비용이 적은 노드를 선택)

개선 전: 한 노드에 대한 최단 거리 테이블로 1차원 리스트 사용 O(N^2)

개선 후: 우선순위 큐 사용 O(NlogN)

알고리즘 원리

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
4. 3의 노드를 거쳐가는 비용을 계산해서 최단 거리 테이블 갱신
5. 3,4 과정 반복