다익스트라 알고리즘

: 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘

특징

• 그리디 알고리즘 (매번 가장 최단 거리를 가진 정점을 선택하여 처리)
• 양의 가중치를 가진 그래프에서 사용
• 시간 복잡도: O(V^2) V: 그래프의 정점의 수

다익스트라 알고리즘 변수들

• distance: 시작점에서 이 노드까지의 거리

  → 특정 노드까지의 “최단 거리 예상치” (현재까지 아는 정보로 계산한 최단 거리)

  • 예시) A B D 경로는 찾았지만, A C D 경로는 아직 못 찾았다고 가정

  

  → D.distnace = 6

• predecessor: 현재까지 찾은 최단 경로에서 바로 직전의 노드

  • 위의 예시) D.predecessor = B

• complete: 노드까지의 최단 경로를 찾았다고 표시하기 위한 변수

  • 처음에는 모두 False

엣지 Relaxation

: 노드들을 방문하면서 해당 노드의 distance, predecessor를 바꾸는 것

• A에서 B를 방문할 때, B의 변수를 업데이트 해주는 것

  : 엣지 (A, B)를 relax한다.