Dijkstra

Dijkstra : 그래프의 최단거리 알고리즘(출발 노드와 모든 노드간)

데이스크라 (Dijkstra)

• 그래프에서 최단 거리를 구하는 알고리즘

• 기능 : 출발 노드와 모든 노드간의 최단 거리 탐색

• 특징 : 음수의 가중치를 가지는 간선이 없다 -> 존재한다면 사용불가능

  • 음수까지 하고싶으면 벨만-포드 알고리즘

• 시간 복잡도 :

  • 인접행렬 : $O(V^2)$

  • 인접리스트 : $O(E * logV)$

    • V : 노드 수

    • E : 에지 수

다익스트라 알고리즘은 초기에 인접행렬을 사용했고 이후에 우선순위 큐(힙) 등을 이용하는 방법이 탄생했다. GPS S/W나 네트워크에서도 많이 사용한 알고리즘으로 구현부분에서 실수가 많이 발생한다.

구현 방법

(1)

먼저 1번 정점을 선택한다. 자기 자신의 비용은 0으로 초기화 하고 방문을 체크한다. 1번 정점에서 5, 6번 정점은 바로 이어져 있지 않기 때문에 무한대(INF)로 표시한다.

visit = 1
1까지 거리 = 0
2까지 거리 = 2
3까지 거리 = 5
4까지 거리 = 3
5까지 거리 = INF
6까지 거리 = INF

(2)

방문한 곳(1번)에서 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택한다. 가장 짧은 2번 정점을 선택하게 되면 1-2-6이 연결되면서 6의 비용이 12로 바뀐다. 3번 정점까지도 1-2-3으로 갈 수 있지만 기존의 비용 5가 2번을 통해 가는 7보다 작기 때문에 비용은 그대로 유지시킨다.

visit = 1, 2
1까지 거리 = 0
2까지 거리 = 2
3까지 거리 = 5
4까지 거리 = 3
5까지 거리 = INF
6까지 거리 = 12

(3)

다시, 1과 연결된 가장 가까운거리 4번을 방문한다. 그리고 갈 수 있는 정점들의 비용을 갱신한다.

visit = 1, 2, 4
1까지 거리 = 0
2까지 거리 = 2
3까지 거리 = 5
4까지 거리 = 3
5까지 거리 = 10
6까지 거리 = 12

이것을 계속 반복하면 다음과 같은 결과가 나온다.

visit = 1, 2, 4, 3, 5, 6
1까지 거리 = 0
2까지 거리 = 2
3까지 거리 = 4
4까지 거리 = 3
5까지 거리 = 6
6까지 거리 = 8