Starting with tentative distances
The source begins at distance zero and other vertices at infinity. Relaxing an edge from u to v asks whether reaching u and then taking that edge improves the best known distance to v. An improvement updates both distance and predecessor.
Relaxation compares cumulative source-to-vertex cost, not merely the cheapest neighboring edge. Predecessors recover a path afterward, while an unreachable target retains its unreachable status rather than being assigned zero cost.
References: [1]
Nonnegative weights justify settling
The standard method repeatedly selects the unsettled vertex with smallest tentative distance. Nonnegative remaining edges prevent an unfinished detour from lowering that selected minimum, allowing its shortest distance to be settled.
A priority queue supports minimum selection and must reflect distance improvements through its update rules. Zero weights are permitted. The standard nonnegative-weight guarantee does not automatically extend to arbitrary negative edges or modified algorithms.
Representation and query scope affect cost
Adjacency lists with a suitable binary-heap priority queue give the common O((V+E) log V) bound. Initialization, comparisons, and edge access remain part of implementation cost, while different representations or queues can have different bounds.
For one destination, search can stop when its distance is settled, not merely when the destination is first discovered. The optimized quantity is the modeled sum of edge weights, which must consistently represent the intended time, cost, or other objective.
References: [1]