Dijkstra Algorithm

weighted graph가 주어졌을 때, 하나의 src vertex에서 다른 모든 vertices로 가는 최소 비용을 구하는 알고리즘

pseudo-code

1. Set dist[source]=0 and all other distances as infinity.
2. Push the source node into the min heap(priority queue) as a pair <distance, node> → i.e., <0, source>.
3. Pop the top element u (node with the smallest distance) from the min heap.
	1. If dist[u] < dist of element<d,u>: Continue (불필요한 element 조사x)
	2. For each adjacent neighbor of the current node:
		Calculate the distance using the formula:
        newDist = dist[u] + weight[u][v]
            If this new distance is shorter than the current dist[v], update it.
            Push the updated pair <dist[v], v> into the min heap
4. Repeat step 3 until the min heap is empty.
5. Return the distance array, which holds the shortest distance from the source to all nodes.

시간 복잡도

O(ElogV)

주의

Negative Weight

음수 가중치가 있을 때, cycle이 존재하면 쓸 수 없다.
Bellman Ford algorithm을 사용해야 한다.

vs BFS

최단 거리 문제하면 보통 BFS 아니면 Dijkstra를 사용한다.
edge 에 weight가 없으면 단순 BFS,
weight가 있으면 Dijkstra를 쓰면 된다. ex

Examples