[개념] Dijkstra(다익스트라) - python

다익스트라 알고리즘

- 유향 그래프에서 간선들의 가중치가 모두 0 이상인 경우의 최단 경로 알고리즘

 

 

 

왜 가중치가 0 이상이어야 할까?

 

- 다익스트라 알고리즘에서 최단 거리를 저장한 노드는 집합에 포함시켜 놓는데, 집합에 포함된 노드의 최단 거리 값은 다시 계산하지 않는다. 그러나 가중치가 음수일 경우, 최단 거리 값이 바뀌어 노드에 저장해 놓은 최단 거리 값을 바꿔야하는 경우가 발생할 수도 있다. 하지만 집합에 포함된 노드는 값을 수정할 수 없기 때문에 다익스트라 알고리즘은 간선의 모든 가중치가 0 이상일 때 성립한다.

 

 

 

다익스트라 알고리즘에서의 가정 

 

두 정점 간 경로가 존재하지 않으면 경로의 가중치는 무한대로 정의한다.

두 정점 간 간선이 존재하지 않으면 가중치가 무한대인 간선이 존재한다고 간주한다.

 

 

 

다익스트라 알고리즘 진행 과정

 

1. 모든 노드를 무한대로 초기화한다.

2. 시작 노드에 거리 값 0을 넣어준다.

3. 자신과 인접한 노드에는 모두 거리 값을 넣어준다.

4. 인접한 노드 중 가장 작은 거리 값을 가진 노드를 집합에 포함 시킨다. 자신과 인접한 노드 중 최단 거리의 노드를 선택한다. 

5. 3번과 4번 과정을 반복하다, 집합의 노드의 개수가 전체 노드의 수와 같아지면 종료한다.

 

 

초록색 배경 - 집합 / 회색 노드 - 인접 노드 / 초록 노드 - 현재 노드 / 점선 간선 - 간선을 지나기 전 노드가 집합에 포함돼 사용하지 않는 간선

 

 

그림 (j)는 각 노드까지 이르는 최단 거리를 형성하는 그래프이다. 

이는 각 노드들이 마지막으로 회색으로 표시되던 시점에 사용된 간선들이다.

 

 

이제 알고리즘을 구현해보겠다.