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 (불필요한 adjNode 조사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.

주의

Negative Weight

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

vs BFS

문제에서 src to dst 사이 최단 거리를 요구할 때,
edge 에 weight가 없으면 단순 BFS, 있으면 Dijkstra를 쓰면 된다. ex

Examples