[알고리즘] 최단 경로 알고리즘

최단 경로 알고리즘 (Dijkstra)

최단 경로(shortest path)문제 란?

임의의 두 노드를 연결하는 경로 중, 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.

여기서 가중치는 비용, 거리, 시간 등이다.

예를들어 위와 같은 그래프에서 A -> B로 가는 경로를 생각해보자.

A->B로 갈 수 있는 경로는 매우 많다. 하지만 그 중에서 최단 경로는 노드 E를 거쳐서 가는 경로이다.

최단 경로를 구하는 문제는 여러가지가 있다.

1. 하나의 노드 -> 다른 하나의 노드 최단 경로 찾기
2. 하나의 노드 -> 다른 모든 노드 최단 경로 찾기
3. 하나의 목적지로 가는 모든 최단 경로 찾기
4. 모든 최단 경로 찾기

Dijkstra의 최단 경로 알고리즘

개념

Dijkstra의 최단 경로 알고리즘은, 위의 최단 경로 문제들 중에서 2번. 하나의 노드에서 다른 모든 노드들의 최단 경로를 구하는 알고리즘이다.

기본 로직

• 최단 거리를 기록하는 배열 dis 이용
• 시작 노드 v
• 집합 S ={최단 거리에 해당하는 노드들이 하나씩 추가됨}

1. dis[v] = 0 , S={v}

   자기 자신과의 거리는 0

2. v와 연결되어 있는 다른 노드에 대한 dis 값 = v와 해당 노드 사이 간선의 가중치

   v와 연결되어있지 않은 다른 노드에 대한 dis 값 = 무한대의 값

3. 매 단계에서 S에 포함되지 않은 노드 중에 dis가 가장 작은 값을 S에 추가

4. 새로운 노드 u가 S에 추가되면, S에 포함되지 않은 다른 노드들의 dis값을 수정

   • 시작점이 u로 바뀌었기 때문에, u를 거쳐서 가는 거리와 기존의 거리를 비교해서 더 작은 값으로 dis를 갱신
   • dis[w] = min(dis[w], dis[u] + weight[u][w])

구현

1. 우선순위 큐
2. visited[] 이용
   • 정점의 수가 적거나, 간선의 수가 매우 많은 경우 이 방식이 더 빠를 수 있다

시간복잡도

• 노드 개수 V, 간선 개수 E일 때

   

1) 배열을 이용하는경우

시간복잡도 : O(V^2)

2) 힙(우선순위 큐)를 이용하는경우 

시간복잡도 :  O(ElogV)

참고 자료

https://hsp1116.tistory.com/42

https://mattlee.tistory.com/50

https://sungjk.github.io/2016/05/13/Dijkstra.html

https://wordbe.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98