[ 알고리즘 ] 18. Shortest path - Dijkstra Algorithm

Dijkstra Algorithm
( From all to all )

● 조건

:  Negative weight인 edge가 없다면,

   Bellman-Ford보다 성능이 좋다.

 

 

● 구현법

- Queue에 담긴 Vertex 를 하나씩 꺼내면서 Tree를 키운다.

- Queue는 , d[v] 가 낮은 순서대로 Prioirity queue를 만든다.

 

Minimum shortest path인 것을 select한다.

u라는 vertex를 S에 넣은 뒤 , u와 인접한 모든 node를 Relaxation 시킨다.

 

1 : 초기화

2,3 : set을 비우고, Q에 vertex들을 넣는다.

 

4 ~ 8:  Q에 vertex가 비어있지 않았다면, 

            vertex하나를 꺼내고, 그걸 S에 넣는다.

 

   7~8 :  그 vertex와 인접한 vertex들에 대해

             Relax시킨다. 

 

 

---

예제 1 )

 

 

 

1단계 : 초기화 시킨다.

 

 

 

 

2단계 : Q가 비어있지 않다면, 하나를 꺼내 S에 넣는다.

 

 

 

3단계 : S에 해당 vertex를 넣고, 인접한 node를 Relax한다.

 

 

다시 2단계 : Q가 비어있지 않다면, 하나를 꺼내 S에 넣는다.

 

 

 

반복...

 

 

결과 ▼ 꼭 해보기1!!!

 

 

---

Negative Edge면 안 되는 이유

 

 

 

 

 

---

Time Complexity

 

 

 

lg V인 걸 Edge 수만큼 해야하므로 

O(E lg V)