DSA Notes

Graphs

Dijkstra

Shortest paths when edges have non-negative weights.

The idea

Dijkstra’s algorithm finds the shortest distance from one start vertex to every other vertex. All edge weights must be non-negative.

Keep dist[u], the best distance known so far, and a min-priority queue of pairs (distance, vertex). Pop the closest unfinished vertex: its distance is final, because any other route would pass through a vertex at least as far away. Then try to improve its neighbours.

With a priority queue the cost is O((V + E) log V).

Sample problem

743. Network Delay Time ↗ Medium

A signal is sent from node k through a network of directed edges, each with a travel time. Return the time at which the last node receives it, or −1 if some node never does.

times = [[1,2,4],[1,3,1],[3,2,2],[2,4,1],[3,4,5],[4,5,3]], n = 5, k = 1
output = 7

Why the solution works

Each node first hears the signal along its shortest path from k, so the answer is the largest shortest-path distance.

Dijkstra’s algorithm finalises nodes in order of distance. The closest unfinished node cannot be improved: any other route would pass through a node at least as far away, and edges never have negative time.

A min-priority queue hands over that closest node. Outdated queue entries are skipped by comparing them with the best known distance.

Complexity: O((V + E) log V) time, O(V + E) memory.

Watch out

  • A negative edge breaks the argument that a popped distance is final.
  • Skip stale queue entries, or the running time degrades badly.
  • Distances can exceed int: use long long, and a min-heap (greater<>).
Watch it run

Practise on LeetCode