Dijkstra 알고리즘

δ(A, B) : A->B로 가는 최단경로

w(A, B) : A와 B 사이의 연결된 edge의 weight

               if) A와 B 사이에 연결된 edge의 weight = 5 -> w(A,B) = 5

               if) A와 B 사이에 edge가 X -> w(A, B) = ∞ (갈 수 없으므로)

 

Single-Source Shortest Paths

시작 정점(s)이 하나 주어졌을 때, s에서 다른 모든 노드로 향하는 shortest path를 찾는 문제
 

Dijkstra Algorithm

- S라는 이미 방문한 정점들에 대한 set 유지 -> 처음엔 비어있고, 시작과 동시에 시작 정점이 s에 들어가게 된다.

- D라는 distance array를 정점 수만큼 유지 -> D[i]는 현재까지 밝혀진 경로들 중 최단 경로 (d(s,i)인 s에서 i까지인 거리를 유지

- 알고리즘을 노드 수만큼 반복

- 매번 반복문을 돌 때마다, 방문한 노드의 이웃들의 거리를 갱신해주는 작업 수행 (relax)

- relax(u, v, w)  

   If d(s,v)>d(s,u)+w

               9    >         5 + 2

           d(s,v)=d(s,u)+w (새로 알게 된 경로가 더 짧은 거니까 update 수행)
           prev(v) = u (s에서 v노드까지 오는데 바로 앞에 있는 노드를 u로 세팅)

 

 

- 만약 노드 u를 방문 했다면, 지금까지 알고 있는 최단거리와 실제 최단거리는 같다. d(s,u) = δ(s,u)

 

Dijkstra Algorithm- example

Dijkstra Algorithm- sudo code

 function Dijkstra(G, r): // G = 그래프, r = 시작정점
   S = {r} // set에 시작정점인 r 삽입
   initialize an array D of size |V| with infinity 
   // D라는 배열의 사이즈는 V(노드 수), D의 초깃값은 모두 무한대로 세팅
   initialize an array prev of size |V| 
   // prev라는 배열의 사이즈는 V(노드 수), prev의 초깃값은 상관 X
   
   D[r] = 0 
   // 시작정점 -> 시작정점으로 가는 거리는 0 
   while S != V: // 이 과정은 노드 수만큼 반복
   u = minNode(V-S, D) 
   // 아직 방문하지 않은 노드(V-S)들 중 D(거리)를 살펴봤을 때, 가장 거리가 짧은 노드를 찾아서 u로 지정 --> minheap으로 찾음.
   add u to S // 해당 노드를 S(set)에 추가
   // 11,13 line은 시작정점 r에서부터 u까지 가는 최단 경로를 찾음.
   for v in G.neighbors(u): // u의 이웃들을 방문하며
   if v is not in S and D[u] + w(u,v) < D[v]: 
   // v(u의 이웃들 중 하나)가 아직 방문하자 않은 노드이고, 지금까지 알고 있는 v(이웃)까지의 거리가 u까지의 거리 + u에서 v로 가는 weight보다 크다면
   		D[v] = D[u] + w(u,v) // v(u의 이웃들 중 하나)의 거리 update
		prev[v] = u