Shortest Path

  • Dijkstra algorithm
  • Versions of Dijkstra
    • only shortest path length for each node
    • actual path for each node also
    • all possible shortest paths for each node
  • Alternate explanations
    • as a variation of BFS
    • select from nearest to furthest

Dijkstra algorithm

src node가 있고, 다른 노드로 가는 shortest path를 찾아라

의문점: src노드는 왜 하나일까?

다익스트라 알고리즘은 모든 목적지로 가는 shortest path를 다 구한다.

왜? –> shortest path의 모든 부분은 shortest path이다. 한 군데로 가는 shortest path를 구하면 굉장히 많은 곳으로 가는 shortest path를 구한 것이다. 따라서 한 군데로 가는 shortest path를 구하라는 거나 모든데로 가는 shortest path를 구하라는 건 다른게 아님.

Versions of Dijkstra

다익스트라 알고리즘은 꽤나 복잡하다. 다익스트라 알고리즘은 원래 길을 찾는 알고리즘인데, 대부분의 책에서는 path를 찾는 대신 path의 길이를 구한다. 왜냐하면 길까지 구하는 걸로 금방 바꿀 수 있기 때문이다. 심지어 shortest path가 여러 개 있는 경우에도 모든 path를 다 찾을 수 있다!

Pseudocode (길이만 구하는 경우)

/*
G: input graph
n: node의 수
v0: src node
dmin(v): v와 인접한 blue node들 중 weight가 가장 작은 edge의 값
*/

Algorithm Dijkstra(G, n, v0, dmin)
	/// init
	for u in V do 
		dmin(v) <-g(v0, u) /// g는 weight. edge가 없을 시 무한대임
	R <- {v0} // dmin(v) is red for red nodes

	/// red node를 하나씩 늘려감
	while |R| < n do 
		among nodes not in T, find u with smallest dmin(u) /// 엄청 간단한 greedy.
		R <- R U {u}
		for w not in R do 
			dmin(w) <- min[dmin(w), dmin(u)+g(u, w)]
		// dmin(w) is blue for blue nodes

red node: 최종 정답을 아는 node. red number를 가짐
blue node: 아직 최종 정답을 모르는 node. blue number를 가짐
red number: 최종 정답
blue number: red node들만을 거쳐 올 수 있는 가장 짧은 path의 길이 (모든 red node들을 거쳐오는 건 아님! blue node들을 거칠 수 없다는 의미이다.)
T: red node들의 집합. T에 안 들어가면 blue node이다.
이미 알고 있는 사실: src node까지의 거리는 0이다.

Proof

위의 슈도코드에서

among nodes not in T, find u with smallest dmin(u)
T <- T U {u}

는 blue node들 (nodes not in T) 중에서 가장 작은 blue number를 갖는 노드를 찾아 red로 칠한다. 이때 greedy한 방법으로 사용했는데, 이 방법에 대한 정당성을 증명해보자.

red node에 0, 8, 10이, blue node에 15, 17, 19, 20이 있다고 하자. 1

현재 blue node들 중에서 dmin값의 최소는 15이므로, 15가 선택될 것이다. 이는 두 가지 의미로 이해할 수 있다:

  1. red node들만 거쳐 오는 가장 짧은 길이가 15이다.
  2. blue node들 중 가장 작은 값이 15이다.

2

그런데 왜 15가 정답일까? 다른 값이 정답이 될 수 없을까? 라고 의문을 가질 수 있다.

이는 proof by contradiction을 통해 15밖에 정답이 될 수 없음을 증명할 수 있다.
만약 답이 15(red node들만 거쳐옴)가 아니라면, 즉 더 좋은 답이 존재한다면 이 답은 blue node를 거쳐 오는 것 중에 있다. blue node를 거치는 path가 어떤 것이든 간에 path를 구성하면서 red node들만 거친 순간이 있다.

이때 20이 정답이라 가정하자.

3

그런데 20 >= 15이므로, 15가 min값이라는 가정에 모순이다. 따라서 15가 정답이 되어야 한다.

15를 처리하고 나서도 각각의 blue node에 대해, g(w)는 여전히 red 노드만을 통해 src에서 w까지의 shortest path이다. 따라서 15를 통과하지 않는 path 중 더 짧은 path가 있다면 이미 찾았을 것이며, 15를 통하는 path보다 더 짧은 path가 존재한다면 15를 처리할 때 갱신되었을 것이기 때문이다.

15가 red에 들어온 상태이다. 4

그럼 이제 17, 19, 20을 순서대로 넣어주면 되지 않을까?
정답부터 말하면 절대 안된다.

원래 17이라는 값은 0, 8, 10만 가지고 올 수 있는 짧은 길이였다.
근데 15가 red node가 되면서 red들의 집합이 업데이트 되었으므로 17은 이제 valid한 숫자가 아니다. 15때문에 더 좋은 path가 생길 수도 있기 때문이다.
그래서 red node가 추가될 때마다 blue number들을 업데이트 해줘야 한다. blue number의 정의는 red node들만 거쳐가는 가장 짧은 path의 길이인데, red node가 추가되면 가장 짧은 길이가 달라질 수 있다.

이 과정은 슈도코드 상에서 아래의 부분에 해당한다.

    for w not in T do 
        dmin(w) <- min[dmin(w), dmin(u)+g(u, w)]
        // dmin(w) is blue for blue nodes

dmin(w)는 원래 알고있는 값(17), dmin(u)는 방금 추가된 red number(15)를 의미한다.
업데이트할 때는 방금 추가된 red number와 인접한 blue node들만 업데이트하면 된다. 0-8-10-15처럼 방금 추가된 red node를 중간에 거치는 경우는 고려하지 않아도 된다. 즉 방금 추가된 node를 마지막으로 거치는 것만 고려하는데, 왜그럴까?
방금 추가된 red node보다 이전에 추가된 node(10)은 src로부터의 shortest path는 15를 포함하지 않기 때문이다.

다익스트라 알고리즘이 끝나면 전부 red node가 되어 모든 node에 대해 정답을 아는 셈이다.

Find actual path

앞에서는 shortest path의 길이를 찾았으니, 이제 실제 path를 찾아보자.

현재까지 알고 있는 사실은 정확히 어떤 path인지는 모르지만 각각 17과 19짜리 path가 있다는 사실이다. 4

blue number들을 업데이트하자.
17 < 15+4이므로 원래 있던 path가 더 좋으니 값을 갱신하지 않고, 15 + 1 < 16이므로 16으로 update한다.
5

여기서 한 가지 더 생각해볼 수 있다. path 전체는 모르더라도 그 path 중에서 내 바로 앞에 있는 노드는 기억할 수 있다. 16이라는 값과 함께 16은 15를 가지는 노드(A라고 하자)를 통해 온다는 내용도 함께 기억하는 것이다. 그러면 나한테 오는 길이가 16이라는 사실 뿐만 아니라 나한테 오는 노드가 무엇인지도 알게 된다. 6

이렇게 되면 모든 노드가 직전 노드을을 알고 있으므로, 직전 노드들을 거꾸로 따라가면 src에 도달할 수 있고 이것이 shortest path가 된다. shortest path가 여러개인 경우는 직전 노드를 여러개 넣어주면 된다.

Implementation

Prim 알고리즘과 구현법이 꽤나 비슷하다.

/*
G = (V, E, g): node set
두 개의 node과 edge의 weight까지 한꺼번에 입력으로 줬음
--> 이렇게 하면 입력 사이즈가 n^2가 아닌 m이 됨(물론 m이 최대일 때는 n^2이 되긴 함). 훨씬 compact함
n: 노드의 개수. G로부터 알 수 있으므로 따로 인자로 주지 않아도 됨
v0: source 노드
dmin: 출력. n개짜리 배열. 처음에는 무한대의 값으로 초기화하고 알고리즘 종료 후에는 정답이 들어있음
*/

algorithm dijkstra(G, n, v0, dmin) {
	for u in V do 
		dmin(v) <- g(v0, u)
	R <- {v0} // dmin(v) is red for red nodes
	while |R| < n do
		among nodes not in R, find u with the smallest dmin(u)
		R <- R U {u}
		for w not in R do
			dmin(w) <- min[dmin(w), dmin(u) + g(u, w)]
		// dmin(w) is blue for blue nodes
}

그럼 이제 슈도코드를 한 줄씩 뜯어보자.

먼저 초기화를 한다.

for u in V do
	dmin(v) <- g(v0, u)

dmin의 인덱스 값들은 최초에는 무한대의 값으로 초기화되어 있다. 모든 노드들을 돌면서 그래프에 주어진 값으로 초기화한다. (그래프를 초기화하는 작업임)

v0를 red node의 집합에 추가한다.

R <- {v0}

실제 구현할 때는 크기 n 만큼의 배열을 만들어 red node인지 여부를 0/1로 mark하는 방식으로 구현하면 된다. 꼭 필요한 것은 아니지만 mark 배열이 있으면 코딩이 더 쉬워진다.

red node를 하나씩 추가한다.

while |R| < n do

한 번 돌 때마다 red node가 무조건 하나씩 추가되니까 그냥 n-1번 돈다는 소리이다. Prim이나 Kruskal과의 차이점은 다익스트라는 cycle이 없는 것은 버리기 때문에 추가되는 노드의 개수는 언제나 1이라는 것이다.

이제부터가 핵심 부분이다. blue number가 가장 작은 노드를 찾는다.

among nodes not in R, find u with the smallest dmin(u)

blue number가 가장 작은 노드를 찾는다. 어떻게 찾는가?

답부터 말하자면 Prim 알고리즘처럼 priority queue를 사용하면 된다(Kruskal은 sorting).

방금 추가된 노드를 n이라 하자. blue node들 중에서 n과 edge가 direct하게 연결된(adjacent한) 노드들에 대해서만 생각하면 된다(왜 그런지는 지난번에 얘기했음).

dmin(u)를 찾으려면 PQ에 집어넣고 PQ에서 가장 작은 값을 꺼낸다. 그러면 PQ에는 어떤 값들을 집어넣는지 알아야 한다.

PQ에는 지금 막 edge로 업데이트된 값들을 집어넣는다. 여기에 여러 variation이 있는데 큐에 집어넣기에 가장 간단한 버전을 보자.

예를 들어 방금 추가된 노드 n의 값이 30이고, n과 연결되고 red number가 31인 red node를 P라 하자. n과 P를 연결하는 edge의 weight 값은 5이다. 그리고 n과 adjacent한 blue node 두 개를 각각 Q, R라 부르자. Q와 R의 blue number는 각각 36, 40, n과 연결하는 edge의 weight 값은 각각 8, 6이다.

pq_1

pq_2

이 중에서 PQ에 어떤 값들을 넣어야 하는가? 여러 가지 방식이 있지만 나는 enqueue가 쉬운 방식을 택해 구현해 보겠다. 이는 무조건 enqueue한 다음, 적절한 값인지 여부는 dequeue 할 때 고려하는 방법이다.

P는 이미 red node이다. 다르게 표현하자면 P는 n보다 먼저 red node였다. 즉, 이미 답을 찾은 노드이므로 더 좋은 답이 나올 수 없다. n의 edge를 더한 값으로 업데이트를 한다 하더라도 기존의 값보다는 나쁜 결과를 내뱉는다. 그렇지만 값이 좋아지든 나빠지든, red node인지 blue node인지 상관하지 말고 일단 다 PQ에 넣는다.

큐에 (P, 35) (Q, 38), (R, 36)을 다 집어넣는다.

그리고 시작할 때도 큐에 넣어준다. src 노드 v0에 direct하게 붙어있는것도 집어넣어줘야 하니까 for u in V do dmin(v) <- g(v0, u) 에서 (u, g(v0, u))를 큐에 넣어준다.

결과적으로 among nodes not in R, find u with the smallest dmin(u) 은 blue node가 나올 때까지 큐에서 꺼낸다는 의미가 된다.

왜 그럴까? 큐에 어떤 값들이 들어있는지 생각해보자. 큐에는 blue number가 들어있다. 그리고 enqueue할 때 일단 다 집어넣었으므로 red number도 들어있다.

큐 안에는 같은 노드가 여러 개 들어있을 수도 있다. 예를 들어, (R, 36), (Q, 38), (P, 35) 외에도 (Q, 36), (R, 40)이 이미 있을 것이다. 그렇지만 PQ이기 때문에 꺼낼 때는 어차피 숫자가 가장 작은 값이 나올 것이다.

꺼내고 난 다음에는 꺼낸 노드가 red node인지 확인한다.

red node라면 나온 값이 의미없는 값이므로 버린다. 최초의 blue가 나오면 그 값은 무조건 blue 중에서 가장 작은 값이다. R의 경우에는 업데이트 후 좋아졌으니까 36이, Q는 기존의 값 38보다 업데이트된 값 36이 더 작으므로 36이 나올 것이다.

시간 복잡도

  • 초기화
    • 모든 노드와 엣지를 한 번씩 봄
    • O(m+n)
  • PQ(에서 몇 번 꺼내는가?)
    • PQ에 몇 번 집어넣는지를 계산할 수 있다.
    • 한 노드가 red로 바뀌면 그 노드에 붙어있는 edge들을 다 보므로, 전체적으로는 각 edge를 두 번씩 본다.
      • O(2m) == O(m)
    • PQ에서 2m번을 꺼내므로 PQ에서의 시간 복잡도는 O(m * log n) = O(m log n)

따라서 전체 시간복잡도는 O(m log n + n) = O(m log m)이다.

Alternate explanations

  • from BFS

BFS가 어떤 경우에는 shortest path를 쉽게 찾을 수 있다는거 src node가 하나 있고 큐(PQ아님!)가 하나 있음 우선 src node를 큐에 집어넣고 시작. 그 다음에 src node를 1으로 mark하고 mark와 distance 배열이 있음 bfs는 shortest path를 찾는게 기본 목적이 아닌데 shortest path를 찾는데 활용될 수 있다. 이 경우는 모든 edge의 weight가 1이라고 가정하고 하는거임.

큐에서 노드를 하나 꺼내고 그 노드를 i라 하자. 만약 i가 mark되어있다면, 즉 이미 방문했다면 아무것도 하지 않는다. 그렇지 않다면 i를 mark하고 i의 dist를

i에 인접한 모든 노드 j에 대해 (j, dist[i]+1)을 큐에 집어넣는다.

성능이 다익스트라에서 log만 빠진 O(m+n) 모든 distance가 1일 때 shortest path를 찾음.

weight가 1 아닌 경우에는 어떻게 할까? –> weight가 3이면 weight 1짜리 세 개로 대신하는 식으로 그래프를 바꾸면 된다. 그러면 모든 edge의 weight가 1이므로 BFS를 돌리면 shortest path를 찾을 것이다. 근데 이 방법의 문제점은 시간이 오래 걸린다는 것이다. 만약 노드가 다섯 개 짜기 그래프인데 weight가 백만이라면? –>

Alternate explanations

From BFS

BFS가 어떤 경우에는 shortest path를 쉽게 찾을 수 있다. BFS는 shortest path를 찾는게 본 목적이 아닌데 shortes tpath를 찾는데 활용될 수 있다. 이 경우는 모든 edge의 weight가 1이라고 가정하는 것이다.

그럼 BFS 과정에 대해 간략히 알아보자. BFS에는 그래프와 큐(PQ 아님!), mark와 distance 배열이 필요하다. 먼저 src node를 큐에 집어넣고 src node를 1로 mark한다.
큐에서 노드를 하나 꺼내고 그 노드를 i라 하자. 만약 i가 mark되어있다면, 즉 i를 이미 방문했다면 아무것도 하지 않는다. 그렇지 않다면 i를 mark하고 i의 dist를 증가시킨다. 그런 다음 i에 인접한 모든 노드 j에 대해 (j, dist[i]+1)을 큐에 집어넣는다. 이 과정을 큐가 빌 때까지 계속한다.

BFS의 성능은 PQ가 아닌 일반 큐를 사용하므로 다익스트라에서 log만 빠진 O(m+n)이다. BFS는 모든 노드들 간의 distance가 1일 때 shortest path를 찾는다. 그럼 아래 그림처럼 weight가 1이 아닌 경우에는 어떻게 할까?

bfs_1

그래프를 수정하면 된다. weight가 3이면 weight 1짜리 노드들을 두 개로 대신하는 식으로 그래프를 바꾸자는 것이다. 그러면 모든 edge의 weight가 1이므로 BFS를 돌리면 shortest path를 찾을 수 있다.

bfs_2

그런데 이 방법의 문제점은 시간이 오래 걸린다는 것이다. 노드 다섯 개 짜리 그래프인데 weight가 100만이라면 노드 백만 개를 추가해야 한다.

이를 해결하는 방법을 알아보자. 어떻게 하면 BFS에서 필요없는 계산을 줄일 수 있을까?

일단 그래프 상에서 각 노드마다 src로부터의 distance를 나타내면 다음과 같다.

bfs_3

이 중 새로 집어넣은 노드 (까맣게 칠해진 작은 노드) 말고 원래 있던 노드 S, A, B, C, D가 mark되는 단계를 보자. 이 단계에서만 실제 노드의 값이 바뀌고, 나머지 노드들을 거칠 때는 새로 추가된 노드들이 mark된다. 여기서 새 노드들을 skip하고 original node들로 바로 갈 수 있으면 추가한 노드들이 mark되는 단계를 줄일 수 있다! 그런데 다음 original node를 어떻게 아는가?

이는 edge weight에 써있다! 위의 예시에서 노드 S에 의미있는 edge의 값은 3과 6이 있다. 이 중 minimum 값인 3만큼 건너뛰면 된다. 그 다음에는 C를 mark하면서 3+9=12가 의미있게 된다. 그래서 12를 고려대상으로 집어넣으면 된다. 6과 12 중에서는 6이 먼저 꺼내져야 한다. 그렇기 때문에 우리는 PQ를 사용한다.

정리하자면, edge weight에 따라 노드를 추가해 BFS를 수행하는데, 의미 없는 단계들을 건너뛰면 시간을 줄일 수 있다. 이는 가장 가까이 있는 의미있는 노드를 찾음으로써 해결할 수 있다.

Incidentally

  • Dijkstra selects(finalises) nodes from the nearest (smaller shortest path) to the furthest
  • Why?

가까운 것부터 집어넣자는 작전. At any point any red value <= any blue value가 성립한다. 왜일까? 그림에서처럼 방금 red node가 된 노드를 X라고 하고, X와 인접한 blue node들을 각각 Y1, Y2, Y3, Y4라 하자.

incidentally_1

X가 red node가 되면서 Y들의 값이 업데이트 될 수 있다. Y3의 값이 업데이트 되었다고 가정하자. 업데이트 되었더라도 Y3 = X+★ >= X이기 때문에 여전히 X보다 크거나 같다.

incidentally_2

다음 라운드에 Y가 들어오면 Y는 Y1, Y2, Y3, Y4 중에서 선택되므로 X값보다 큰 값이 들어온다. 모든 인접한 노드들에 대해 이와 동일하게 적용되므로, 다익스트라에서는 blue node가 red node로 바뀌는 순서대로 나열하면 distance가 감소하지 않는다(같거나 증가한다).

Finalise node from nearest to furthest

  • The next nearest node is directly connected to the one of the known nodes 여기서 finalise란 path의 길이를 정한다는 의미이다.

그래프에서 어떤 한 순간의 노드들을 보자. 그래프에는 finalise된 red node들과 finalise되지 않은 blue node들이 있다. 현재 blue node들 중 distance가 가장 작은 것을 X라 하자. S에서 X까지 가는 shortest path 중에 unfinalise된 노드가 존재 가능할까? 없다는 것을 proof by contradiction으로 증명해보겠다.

shortest path 중에 unflinalise된 노드가 있다 가정하고 그 노드를 ★이라 하자. shortest path의 모든 부분은 shortest path이므로 src에서 ★까지 가는 shortest path도 shortest path이다.
그런데 ★까지 가는 shortest path가 더 짧으로 unfinalise된 노드가 있으면 X가 가장 작다는 것에 모순이다. 따라서 unfinalise된 노드가 있을 수 없다. 전부 다 finalised node이다. 이미 finalise된 노드와 direct edge를 갖는 걸 전부 다 고려하면 그 중에 가장 작은 것이 X에 온다.

Prim vs. Dijkstra

Prim에서나 Dijkstra에서나 이미 연결되지만, 그 이유는 다르다. 실제로 노드가 finalise되는 순서도 다르다.

Prim

  • 지금까지 들어간 것과 인접한 edge들 중 edge weight가 가장 적은 것을 PQ에 집어넣는다.
  • edge weight만 고려한다.

Dijkstra

  • Prim과 코드는 거의 같은데 기준이 다르다
  • 고려 대상이 노드이다. (물론 결국에는 edge를 고려하는 것과 마찬가지이다)
  • (현재 노드까지의 거리 + edge)가 가장 작은 것을 집어넣는다.