= Solution
<Dijkstra's algorithm> solves \b[the single-source <shortest path problem> in a finite weighted graph with nonnegative edge weights]. Given a source $s$, it computes for every <vertex> $v$ the minimum sum of edge weights on a path from $s$ to $v$, reporting $+\infty$ if $v$ is unreachable. Keeping a <shortest-path predecessor> also recovers the corresponding paths. Directed graphs are allowed; an undirected graph can be represented by two oppositely directed edges. Negative edge weights are outside the algorithm's standard correctness assumptions, while zero weights are allowed.
Back to article page
