[자료구조 및 알고리즘] #20 - Shortest Path

1. Dijkstra Algoritm

 

2024.06.02 - [학교 수업/자료구조 및 알고리즘] - 자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue

자료구조 및 알고리즘 #12 - an Application of Heap and Priority Queue

에서 구체적인 다익스트라의 구현에 대해서 작성했습니다.

 

다시 다익스트라를 의사코드로 나타내면 다음과 같습니다:

Dijkstra(G, n, v_0, d_min): 
# G is graph, n is numbers of nodes, v_0 is source
    For u do d_min(u) <- g(v_0, u) 
    # u is a node in the node set V, g(a,b) is the edge weight between node a and b
    R <- {v_0} # R is the set of RED nodes
    while |R| < n do:
    	Among nodes not in R, find u with smallest d_min(u)
        R <- R U {u}
        For w not in R do d_min <- min[d_min(w), d_min(u) + g(u,m)] # w is a blue node

 

여기에서 Red nodes란, source노드에서 출발하는 shortest path의 길이를 이미 아는 노드입니다. 가장 처음 v_0는 red node가 되는데, v_0에서 v_0로 가는 shortest path는 0으로 이미 알기 때문입니다.

Blue nodes는 shortest path를 모르는 노드입니다.

 

위의 의사코드를 하나하나 분석하고 증명해보겠습니다.

 

2. Correctness

 

가장 처음 다음과 같은 코드를 실행합니다.

For u do d_min(u) <- g(v_0, u)

 

이는 v_0와 direct로 연결된 임의의 노드인 u에 대해서, v_0에서 u로 가는 간선의 가중치를 d_min(u)로 저장하겠다는 의미입니다. d_min은 blue nodes들의 path length를 모아놓을 배열입니다. d_min은 또한 red nodes들만 거쳐서 오는 shortest path의 길이기도 합니다. 이 코드는 처음으로 source와 인접하는 노드들을 연산의 대상으로 넣어놓겠다는 의미입니다. 또한 그 값을 v_0와 u의 간선의 가중치로 하겠다는 뜻입니다.

 

그 후 다음과 같은 코드를 실행합니다:

R <- {v_0}

 

v_0를 red nodes set에 추가하겠다는 의미입니다. 이는 red nodes set의 정의를 보면 당연합니다. red nodes들은 source로부터 시작해서 해당 노드로 도착하는 shortest path를 아는 노드들입니다. v_0에서 시작해서 v_0로 끝나는 shortest path length는 0으로 알기때문에 red nodes set에 넣어주고 다익스트라를 시작합니다.

 

while |R| < n do:

 

red nodes set의 개수가 n이 넘을 때까지만 반복하겠다는 의미입니다. 이는 당연합니다. red nodes set의 개수가 전체 노드개수가 되면 모든 노드에 대한 source로부터의 shortest path length를 구했다는 의미이므로, 알고리즘을 종료하면 됩니다.

 

Among nodes not in R find u with smallest d_min(u)
R <- R U {u}

 

d_min()은 연산의 대상이 되는 노드들이 저장되어있는 배열, 사실 PQ입니다.(* 최소값을 구해야해서) PQ에서 red nodes set, R에 들어가있지 않은(* R에 이미 들어가있는 노드를 꺼내면 cycle이 생기는데 이는 shortest path가 아님) 최소값인 노드를 꺼냅니다. 그 꺼낸 u를 R에 넣어줍니다.

 

잠깐만, u를 R에 넣어준다는 것은 source로부터 u까지의 shortest path length를 안다는 의미입니다. 그렇다면 d_min(u)의 값이 shortest path length라는 의미입니다. 어떻게 알 수 있을까요?

 

d_min을 다시 리마인드하자면, d_min(u)값은 사실 red nodes set에 들어있는 nodes들만 통해서 u에 도달한 path의 length입니다. d_min()들의 값들 중 가장 작은 값을 d_min(u)라고 한다면, 이 의미는 R에 들어있지 않고, u가 아닌 노드들 중 임의의 노드 u'에 대해서 d_min(u) < d_min(u')이라는 의미입니다.

 

다시 돌아와서, d_min(u)가 PQ에서 가장 작을 때, u를 R에 넣는다는 의미는, d_min(u)의 값이 source에서 u까지 도달하는 shortest path length라는 의미입니다. 어떻게 그럴 수 있을까요?

 

만약 d_min(u)가 source에서 u까지 도달하는 shortest path length가 아니라고 가정하면(* 귀류법 가정), 다른 노드들을 통해서 u로 도달하는 path가 d_min(u)보다 length가 짧아야 합니다. 이는 R에 들어있지 않고, u가 아닌 노드들 중 임의의 노드 u'를 지나서 u로 도달하는 임의의 path가 있고, 이 path들 중 d_min(u)보다 짧은 path가 있다는 의미입니다. 하지만 이는 모순입니다. u'을 거쳐 u로 도달하는 임의의 path의 length는 반드시 다음과 같이 정의됩니다:

• d_min(u') + ...

하지만 d_min(u')은 d_min(u)보다 큽니다.(* d_min(u)는 PQ에 의해서 뽑힌 d_min()들 중 가장 작은값이기 때문에) 따라서 d_min(u') + ... >= d_min(u) 가 반드시 성립합니다.

 

그렇다면 u'을 거쳐 u로 도달하는 임의의 path의 길이는 d_min(u)보다 길고, 이는 모순.

따라서 귀류법 가정이 모순.

따라서 d_min(u)는 source에서 u까지 도달하는 shortest path length입니다.

 

For w not in R do d_min(w) <- min[d_min(w), d_min(u) + g(w, u)]

 

이는 d_min의 값들을 재할당해주는 단계입니다. 새로운 R이 생겼으므로, d_min의 값들을 다시 바꿔야하기 때문입니다.(* d_min의 정의가 R노드들만 지나는 shortest path length임을 생각하면 당연함) 이때 새로 넣는 값은 u와 directly하게 연결되는 노드 w에 대해서만 재할당이 이루어집니다. 왜 일까요?

 

다른 노드들이 수정되려면 해당 노드들에 대한 shortest path가 u를 지나야합니다. 그래야 재할당하는 의미가 있기 때문입니다. 하지만 해당 노드들의 shortest path가 u를 지나는 경우는 없습니다. 왜냐하면 d_min의 값은 R의 노드들을 이용한 shortest path로 정해져있고, 그 shortest path에서 u를 추가로 또 지나는 path가 기존의 shortest path보다 더 짧을 수는 없기 때문입니다.(* 중간에 노드가 추가로 끼면, 당연히 length가 늘거나 적어도 같아지기 때문에)

 

다시 돌아와서, 직접 연결되어있는 노드 w에 대해서 d_min(w)(* 원래 저장 되어있던 값)과 d_min(u) + g(w, u)중 작은 값을 선택해서 재할당합니다. 이는 당연한데, R에 u가 새롭게 들어왔기 때문에 기존에 R에서 B로 연결되는 간선들에 g(w, u)들이 추가되었습니다. 이 추가된 간선들에 대해 shortest path length를 수정해야합니다.

 

이 모든 과정을 그림으로 나타내면 다음과 같습니다.

Dijkstra

 

3. Finding actual path

 

red에 추가된 노드 u에 대한 direct edge가 있는 노드들의 d_min을 수정할 때, 값을 수정하는 것이 의미하는 바는 다음과 같습니다:

• 해당 노드를 지나는 shortest path에서 해당 노드로 오기 직전의 노드는 u이다.

이런식으로 직전의 노드들을 저장해놓으면 실제 경로를 알 수 있습니다.

 

Finding all possible shortest paths

 

red에 추가된 노드 u에 대한 direct edge가 있는 노드들의 d_min을 수정할 때, 기존의 d_min값과 수정하는 값이 같은 경우는 여러개의 shortest path가 있음을 의미합니다. 따라서 해당 노드를 지나는 shortest path에서 해당 노드로 오기 직전의 노드가 두 개가 됩니다. 만약 그런 노드가 여러개라면 직전의 노드는 여러개가 될 수 있습니다.

 

4. Alternative Explanations

 

1. BFS

 

만약 간선의 가중치가 3이라면, 해당 간선의 source와 target사이에 간선의 가중치가 1인 노드들을 2개 끼워넣습니다.

만약 간선의 가중치가 9라면, 해당 간선의 source와 target사이에 간선의 가중치가 1인 노드들을 8개 끼워넣습니다.

이를 통해 모든 간선의 가중치가 1인 그래프를 만들고,

BFS를 수행한다면 최단 거리를 구할 수 있습니다.

 

하지만, 간선의 가중치가 매우 크고, 그래프의 노드의 개수가 매우 크다면 메모리 초과가 발생할 수 있습니다.

 

2. Incidentally

 

가장 짧은 path를 선택해 나갑니다.

시작 노드인 source node, s에 대해서 임의의 노드 v_i와 v_i+1이 있고, v_i는 i번째 반복에서 R로 추가된 노드, v_i+1은 i+1번째 반복에서 R로 추가된 노드입니다.

그리고 d_i는 v_i의 d_min값, d_i+1은 v_i+1의 d_min값입니다.

 

이때, d_i <= d_i+1임을 증명합니다. 이를 통해 짧은 path만을 선택하면 shortest path를 찾을 수 있음을 증명합니다.

v_i가 R에 추가될 때는 d_i <= d_i+1입니다. 왜냐하면 d_i > d_i+1이면 v_i가 아닌 v_i+1이 추가되었을 것입니다.

d_i+1을 수정할 때는 d_i+1 = min(d_i, d_i + g(v_i, v_i+1))이므로 모든 간선의 가중치가 양수라면, g(v_i, v_i+1)이 양수이고 따라서 d_i+1 >= d_i가 성립합니다.

알고리즘 상에서 d_i <= d_i+1을 깰 코드가 없으므로, 이는 참입니다.

 

Implement

 

위에서 설명한 구현 방법은 노드가 기준입니다. 하지만 간선을 기준으로 하는 구현 방법이 있습니다.

Prim알고리즘 같이 생각하면 되는데,

2024.09.12 - [학교 수업/자료구조 및 알고리즘] - [자료구조 및 알고리즘] #18 - Greedy Algorithms

[자료구조 및 알고리즘] #18 - Greedy Algorithms

 

 

R에서 B로 넘어가는 시점에서 R에서 B로 보내는 메시지를 기준으로 합니다.

 

메시지?

d_min의 값을 수정하기 위해 R의 노드에서 B의 노드로 수정 요청을 보내는 것을 메시지라고 합니다. 이는 제가 그냥 단어 정의한 것입니다. 없는 단어입니다.

 

Prim에서는 R노드 집합에서 B노드 집합과 연결된 노드들 중 간선의 가중치가 가장 낮은 노드를 선택했지만, 다익스트라에서는 R노드 집합에서 B노드 집합과 연결된 노드들 중 path의 가중치가 가장 낮은 노드를 선택하면 됩니다.

 

이런식으로 간선을 기준으로 하면, 구현이 더 간단해진다는 장점이 있습니다.(* 기존 노드를 기준으로 하면 PQ에 d_min값을 수정해야하는 번거로움이 생깁니다.)