Shortest paths from one source when no edge is negative: repeatedly settle the closest unsettled node, then try to shorten its neighbours’ distances through it (relaxation). A min-heap finds the closest node quickly.
- Average time
- O((V + E) log V)
- Space
- O(V + E)