Dijkstra Algorithm

BFS

From BFS에서 시작하여 다익스트라를 증명할 수 있다.

모든 엣지의 weight가 1이라고 할 때 shortest path를 찾을 수 있다. 

 

queue를 사용함

src에서 시작을 해서 src를 0으로 하고, 거리를 아는 것을 다 queue에 넣음.

이후, 또 인접하는걸 모두 넣는다.

거리가 1인 얘들이 전부 queue에 들어가야 거리가 2인 애들이 전부 queue에 들어갈 수 있다. 

1이 전부 나와야 2가 전부 들어갈 수 있다. 2,3,4도 모두 같은 방식으로 queue에 들어왔다가 나옴

 

 

찾을 수 있지만 굉장히 느리다. 

edge weight를 1로 만들기 위해서 dummy node를 중간 중간에 넣어 모든 edge의 weight가 1이 되도록 한다.

> 그래프가 매우 커지고 느려진다. 

 

S에 가까운 것을 하나씩 체크하면서 가다보면 C가 제일 가까운 노드가 된다. 

dummy node와 진짜 노드를 구별하기 위해 queue에 단순히 노드를 넣는 것이 아니라 [C,3]과 같이 몇번째로 도달한 노드(더미노드를 포함)하여 적어 queue에 넣는다. 

그러면 queue는

[C,3], [A,6] ...이 된다. 

dummy node를 체크하는 것을 skip하는 것

[D,8] [D,12] 두 가지 경우가 발생한다. 그래서 먼저 나온 것을 체크하도록 한다. 

 

Incidentally

Dijkstra Selects Node from Nearest (Smaller shortest path) to furthest

 

redset에 들어오는 노드들은 가까운 것부터 들어간다. 

 

pf)

들어간 순서대로 \(v_0\), \(v_1\) ... 으로 이름을 붙임

d\((v_k)\) ≤ d\((v_{k+1})\)이 성립한다. 

\(v_k\)가 들어가는 시점에서 해당 식이 성립한다. 

update에서 바뀌지 않았다면, 원래도 더 멀었기 때문에 그대로 식이 성립하고

update에서 바뀐다면 \(v_k\)의 기준에서 + weight를 한 것이기 때문에 무조건 성립한다. 

 

 

Finalize Node from Nearest to Furthest

The next nearest Node is directly connected to one of the known nodes

첫 라운드를 시작하기 전에

base

S는 거리가 0인 source가 finalize된다.

step

"몇 개"가 finalize 되어있다고 생각하자

즉 \(v_k\)가 finalize되어있다. 

s에서 \(v_{k+1}\)까지 가는 경로는 모두 \(v_0\)부터 \(v_k\) 사이에 나와야한다. 

\(v_{k+1}\)은 나올 수 없다. 거리가 멀수록 더 나중에 나오는데, \(v_{k+1}\)보다 더 거리가 먼 것은 나올 수 없다.

마지막 edge를 보면 이미 finalized 된 것과 direct로 연결된 엣지들만 보면 \(v_{k+1}\)을 찾을 수 있다. (그 중 제일 작은것)

 

Prim vs Dijkstra

이게 현재 상황일 때

prim은 v와 인접한 애들을 확인하기 때문에 2만큼 떨어져 있는 것을 선택하고

dijkstra는 s,v 전체를 보기 때문에 총합이 4인 것이 아니라 3인 노드를 선택한다.