Weighted Edges and Dijkstra's Idea

Dijkstra finds the shortest paths for non-negative edge weights. A PriorityQueue selects the next node with the currently smallest distance. Relaxation updates neighboring distances.

Negative edges require different methods (Bellman-Ford).

Complexity depends on the queue implementation (typically $O((n+m)\log n)$ with a binary heap).

$$d(v)=\min(d(v), d(u)+w(u,v))$$

Where used

Routing (maps, networks), latency-optimized paths, game AI on tiles. The priority queue is the building block; A* extends the idea with heuristics.

Depth

Dijkstra's algorithm maintains tentative distances from the start. It selects the still open node with the smallest distance and tries to improve the paths to its neighbors through relaxation.

The correctness of the final determination is based on the fact that subsequent extensions cannot undercut an already smallest open value with a negative additional path. If such edges are possible, a different method is required.

A priority queue may contain outdated entries if there is no efficient Decrease-Key available. When extracting, these are discarded based on the current distance. This maintains correctness with a simple implementation.

Difficulty levels

1. Perform a relaxation numerically.
2. Justify the selection of the smallest open distance value.
3. Handle outdated priority entries correctly.

Pitfalls

An entry that has been extracted is only up-to-date if its stored value matches the distance table. The method cannot be salvaged for negative weights by simply adjusting the priority.