Shortest Path in Weighted Graph Using Dijkstra’s Algorithm

Dijkstra is valid only when every edge weight is non-negative. Build an adjacency list, set dist[source]=0, set all other distances to infinity, and push (0, source) into a min-heap. Repeatedly pop the smallest pair. If its distance is not equal to the current dist[node], it is stale and should be ignored. Otherwise try every edge (node, next, weight): if dist[node]+weight improves dist[next], update it, record parent[next]=node when a route is needed, and push the new pair. Do not try to delete the old heap pair; the stale-entry check is simpler and correct. At completion, infinity means unreachable. With an adjacency list and binary heap, time is O((V+E) log V) and space is O(V+E). Mention that zero-weight edges are fine, but a negative edge requires a different algorithm.