[Algo] 다익스트라 알고리즘 (dijkstra)

Dijkstra Algorithm

• DP 를 이용한 대표적 최단 경로 알고리즘
• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있음
• 음의 간선 불가능

 

Idea

" 최단 거리는 여러 개의 최단 거리로 이루어져 있다 "

• 출발 정점에서 가장 가까운 정점을 중간 정점으로 했을 때의 거리와 비교하여 최단 거리를 업데이트

 

ex) 출발 정점이 1이고, 1에서 가장 가까운 정점인 4를 중간 정점으로 했을 때,

      3, 5의 경우 1에서 바로 가는 것보다 중간 정점인 4를 거쳐서 가는  것이 더 가까움

      출발 정점인 1에서 3과 5로 가는 최단 거리를 3, 7로 업데이트

 

 

 

 

• 모든 정점에 대해 출발 정점에서 가까운 순서대로 위 동작을 반복하면 출발 정점에서 각 정점까지의 최단 경로를 알 수 있음

1과 가장 가까운 정점	1	2	3	4	5
init	0	2	7	1	10
4	0	2	3	1	7
2	0	2	3	1	5
3	0	2	3	1	5
5	0	2	3	1	5

 

Pseudo Code