[알고리즘/Python] (개념) Dijkstra(다익스트라) 알고리즘 (최단경로 구하기) - Shortest Path

 

다익스트라 알고리즘은 그래프 상 시작 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘.

(그래프 간선의 가중치가 항상 양의 정수 값이어야 함.)

 

시간 복잡도 : O(ElogV) => V: 노드 개수, E: 에지(간선) 개수

 

 

개념 이해를 위해 그래프를 하나 예시로 들어보자

각 노드에서 향하는 정점과 가중치를 인접리스트로 정리해보았다.

 

 

 

1. 출발 노드를 설정하고, 그를 제외한 나머지 노드들을 INF(무한대) 값으로 초기화한다.

 

 

 

2. 거리 리스트에서 아직 방문하지 않은 노드 중 가장 작은 노드를 선택(우선순위 큐에서 데이터 뽑아옴)

연결된 노드들의 최단 거리값을 공식을 이용해 업데이트 (테이블 갱신)

 

 

3. [선택된 노드의 거리 리스트 값 + 에지 가중치] < [연결 노드 거리 리스트 값]일 경우 업데이트 수행

(해당 정점을 거쳐가는 거리가 현재 테이블의 최단 거리 값보다 작으면 그 경로 값으로 교체)

업데이트가 수행되는 경우 연결 노드를 우선순위 큐에 삽입

 

 

 

 

 

4. 2, 3을 계속 반복 (큐가 빌 때까지)

 

 

완성 노드에서 무한대 값을 가지는 경우는 시작 노드에서 방문이 불가한 노드라는 의미이다.

 

완성된 노드 리스트: 1(시작 노드)에서 그 외 나머지 노드까지 가는 최단거리 리스트

 

 

 

출처 : Do it! 알고리즘 코딩테스트 with Python