[파이썬] 최단 경로 알고리즘 : 다익스트라(Dijkstra)

• 하나의 정점에서 다른 모든 정점까지의 가장 짧은 거리를 구하는 알고리즘
• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신하는 기법으로, 너비우선탐색(BFS)과 유사함
  • 첫 정점부터 각 정점 간의 거리를 저장할 배열을 만든 후, 첫 정점의 인접 정점부터 거리를 계산하면서 가장 짧은 거리를 해당 배열에 업데이트 해나간다.
  • 첫 정점의 거리는 0, 나머지는 무한대로 배열을 초기화하고, 우선순위 큐에 첫 정점만 먼저 넣는다.
  • 우선순위 큐에서 정점을 꺼내고, 정점부터 인접 정점까지 거리를 배열에 저장된 값과 비교해 짧은 거리를 업데이트 한다.
  • 거리가 업데이트 된 경우, 해당 정점을 우선순위 큐에 넣는다.
  • 다시 우선순위 큐에서 정점을 하나 꺼내고, 위 과정을 우선순위 큐에 꺼낼 정점이 없을 때까지 반복한다.

 

< heapq 라이브러리를 활용해 우선순위 큐 사용하는 방법 >

 

< 다익스트라 알고리즘 : 출발점과 다른 모든 정점까지 최단거리 >

 

< 다익스트라 알고리즘 : 출발점-도착점의 최단거리와 경로 정보 >