• 다익스트라 알고리즘은 단일 출발 최단 경로 문제
  • 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제
  • 방향이 있는 가중치 그래프
• 조건
  • 0 이상의 가중치를 갖는 그래프
  • 시작정점이 주어져야 함 (복수도 상관 x)
• 결과
  • 시작점에서 모든 점까지의 최단 거리
• 시간복잡도
  • O(ElogV)
• 필요한 정보
  • dist[i] : 시작점에서 i번 정점까지의 가능한 최단 거리 (결과값)
  • 자료구조 D : {(v,d) | 시작점에서 v까지 d만에 갈 수 있음을 확인했다.}
• 순서도

Start 노드에서 각 노드로 가는 가중치(거리)값을 가장 최적으로 만드는 문제

1. 최단거리 배열에 start노드를 넣고 각 노드의 값 무한대값으로 초기화
2. 우선순위 큐를 준비
3. 우선순위 큐에서 팝한 값의 인접 노드의 가중치를 봄
4. 최단거리 배열의 값과 비교해서 업데이트
5. 업데이트에 성공하면 해당 노드를 우선순위 큐에 넣음

<aside> 💡 우선순위 큐 : 최소 힙(Heap), 가중치의 합의 값이 가장 작은 녀석을 언제나 팝할 수 있도록 사용

</aside>

• 강의 코드
• 시간복잡도
  • O(ElogE) → O(ElogV)
• 음수 간선이 있으면 안되는 이유
  • 한 정점이 v로 추출되는 횟수가 한 번이 아님