Editing Shortest path problem (section)

==Algorithms==
Several well-known algorithms exist for solving this problem and its variants.
* [[Dijkstra's algorithm]] solves the single-source shortest path problem with only non-negative edge weights.
* [[Bellman–Ford algorithm]] solves the single-source problem if edge weights may be negative.
* [[A* search algorithm]] solves for single-pair shortest path using heuristics to try to speed up the search.
* [[Floyd–Warshall algorithm]] solves all pairs shortest paths.
* [[Johnson's algorithm]] solves all pairs shortest paths, and may be faster than Floyd–Warshall on [[sparse graph]]s.
* [[Viterbi algorithm]] solves the shortest stochastic path problem with an additional probabilistic weight on each node.

Additional algorithms and associated evaluations may be found in {{harvtxt|Cherkassky|Goldberg|Radzik|1996}}.