Edge-Weighted Graph에서의 최단경로를 찾는 Dijkstra Algorithm

그래프 G 상에서 vertex u에서 v로의 가장 짧은 path의 길이를 찾는 문제를 최단경로 문제라고 한다.

 

최단 경로 문제는 주로 1️⃣ edge에 weight가 존재하는지 2️⃣ edge weight 범위가 0이상인지/정수인지 3️⃣ 특정 vertex u에서 도달 가능한 path만 구하는지/모든 vertex set에 대해 구하는지 에 따라 사용할 알고리즘을 정하게 된다.

그 중 Dijkstra Algorithm은 edge에 weight가 존재하면서, 범위가 0 이상 이고 특정 vertex u에서 도달 가능한 vertex들의path를 구할 때 사용하는 알고리즘이다.

출처: https://www.101computing.net/wp/wp-content/uploads/Dijkstra-Algorithm-Graph.png

위 그림과 같은 형태에서 vertex f -> d로의 path는 여러 형태가 존재할 수 있지만, shotest path는 f-b-a-c-d(19)로 유일하다.

이를 구현하기 위한 다익스트라 알고리즘의 idea는 다음과 같다.

 

Dijkstra algorithm: Vertex u에서 graph G의 모든 다른 vertex 간의 shortest path의 길이를 계산한다.

• graph의 vertex들을 방문하면서 vertex u에서 다른 모든 vertex까지의 shortest path의 길이를 지속적으로 업데이트 한다.
  • 처음에는 vertex u에서 u까지의 path의 길이는 0, 나머지는 무한대(INF)로 둔다.

Vertex	vertex u에서 해당 vertex까지 shortest path의 길이	vertex 방문 여부
0(시작 vertex라고 가정)	0	X
1	∞	X
2	∞	X
...	∞	X
N	∞	X

 

이후 Relaxation 과정을 거친다.

• 현재 방문 안 한 vertex들 중 현재 저장된 u에서의 shortest path의 길이가 가장 짧은 vertex v를 방문한다.
• 현재 vertex u에서 v를 제외한 나머지 모든 방문하지 않은 vertex w에 대해 vertex u에서 w까지의 shortest path의 길이를
  • 1️⃣ 현재 u에서 w까지의 shortest path 길이
  • 2️⃣ (u에서 v까지의 shortest path 길이) + edge (v, w)의 weight(해당 edge 존재시)
  • 1️⃣과 2️⃣ 중 작은 값으로 update

 

Vertex	vertex u에서 해당 vertex까지 shortest path의 길이	vertex 방문 여부
f	0	X
b	5 = min of ∞ and 0+5	X
z	16	X
...	∞	X
N	∞	X

위의 그래프에서는 시작 vertex f와 incident한 vertex b와 z에 대해 shortest path길이의 update가 발생했다.

 

이 때, 

Key Lemma:

Dijkstra Algorithm에서 아직 방문 안한 vertex들 중 현재(저장된) vertex u에서부터의 shortest path 길이가 가장 짧은 vertex를 v라 하면 그 길이는 실제 u에서 v로의 shortest path의 길이와 같다.
(v를 방문하면 u-v까지의 shortest path의 길이가 확정된다)

가 성립한다.

즉, 위의 형태에서는 f를 방문한 뒤 vertex b로의 path 길이가 가장 짧다. 이것이 곧 vertex f에서 b로의 실제 shortest path 길이와 같다는 것 이다.

 

다익스트라 알고리즘 증명

출처: 소프트웨어학과 자료구조 강의자료

👉 Base case:

처음 step에서는 무조건 vertex u(시작 vertex)를 고른다(나머지 vertex로의 distance는 무한대).

모든 edge의 weight가 0 이상이므로  vertex u에서 u까지의 제일 짧은 거리는 0보다 작을 수 없음

 

👉 Common Case:

위의 Lemma가 거짓이 아니라고 가정하고, 그것이 성립하지 않음을 통해 실질적으로 참임을 증명하는 귀류법을 사용한다.

Vertex v를 방문할 시 현재 저장된 u에서 v로의 path를 P라 하고, 이보다 더 짧은 path P'이 있다고 가정하자.

이 때, 경로 P'에서 v 직전에 방문하는 정점을 v'이라고 한다. 다익스트라 알고리즘이 수행되면서 v보다 v'를 먼저 방문하고, v'와 v가 인접하므로 P'의 길이가 최단 경로로 저장된다.

따라서 v' 다음으로 v를 방문할 때 에는 경로 P의 길이가 u - v 사이의 최단경로로 업데이트 되지 않는다 ❗❗

 

Lemma가 거짓이라고 가정할 때 모순이 발생하므로, Lemma "방문하지 않은 정점들 중 최단 경로가 가장 짧은 정점 v를 방문할 때의 길이는 실제 최단 경로와 같다"는 참이다

 

Dijkstra's Algorithm Pseudocode

procedure Dijjkstra(G, u, v):	
    Input: u and v is vertex in V(G), 
    Output: find path and cost from u to v
    
    for all U ∈ V:
    	dist(U) = INF
    dist(u) = 0
    
    H = makequeue(V)		(priority queue, using edge-weight as keys)
    while H is not empty:
    	cost, node = deletemin(H)
        
        for edge {cur, next} ∈ E:
        	if dist(cur) + w(cur, next) < dist(next):
            	dist(next) = dist(cur) + w(cur, next)
                insert(H, next)