Editing Dijkstra's algorithm (section)

== Related problems and algorithms ==
Dijkstra's original algorithm can be extended with modifications. For example, sometimes it is desirable to present solutions which are less than mathematically optimal. To obtain a ranked list of less-than-optimal solutions, the optimal solution is first calculated. A single edge appearing in the optimal solution is removed from the graph, and the optimum solution to this new graph is calculated. Each edge of the original solution is suppressed in turn and a new shortest-path calculated. The secondary solutions are then ranked and presented after the first optimal solution.

Dijkstra's algorithm is usually the working principle behind [[link-state routing protocol]]s. [[OSPF]] and [[IS-IS]] are the most common.

Unlike Dijkstra's algorithm, the [[Bellman–Ford algorithm]] can be used on graphs with negative edge weights, as long as the graph contains no [[negative cycle]] reachable from the source vertex ''s''. The presence of such cycles means that no shortest path can be found, since the label becomes lower each time the cycle is traversed. (This statement assumes that a "path" is allowed to repeat vertices. In [[graph theory]] that is normally not allowed. In [[theoretical computer science]] it often is allowed.) It is possible to adapt Dijkstra's algorithm to handle negative weights by combining it with the Bellman-Ford algorithm (to remove negative edges and detect negative cycles): [[Johnson's algorithm]].

The [[A-star algorithm|A* algorithm]] is a generalization of Dijkstra's algorithm that reduces the size of the subgraph that must be explored, if additional information is available that provides a lower bound on the distance to the target.

The process that underlies Dijkstra's algorithm is similar to the [[Greedy algorithm|greedy]] process used in [[Prim's algorithm]]. Prim's purpose is to find a [[minimum spanning tree]] that connects all nodes in the graph; Dijkstra is concerned with only two nodes. Prim's does not evaluate the total weight of the path from the starting node, only the individual edges.

[[Breadth-first search]] can be viewed as a special-case of Dijkstra's algorithm on unweighted graphs, where the priority queue degenerates into a [[FIFO (computing and electronics)|FIFO]] queue.

The [[fast marching method]] can be viewed as a continuous version of Dijkstra's algorithm which computes the geodesic distance on a triangle mesh.

=== Dynamic programming perspective ===
From a [[dynamic programming]] point of view, Dijkstra's algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the '''Reaching''' method.<ref name="sniedovich_062">{{cite journal |last=Sniedovich |first=M. |year=2006 |title=Dijkstra's algorithm revisited: the dynamic programming connexion |url=http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf |journal=Journal of Control and Cybernetics |volume=35 |issue=3 |pages=599–620}} [http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html Online version of the paper with interactive computational modules.]</ref><ref name="denardo_032">{{cite book |last=Denardo |first=E.V. |title=Dynamic Programming: Models and Applications |publisher=[[Dover Publications]] |year=2003 |isbn=978-0-486-42810-9 |location=Mineola, NY}}</ref><ref name="sniedovich_102">{{cite book |last=Sniedovich |first=M. |title=Dynamic Programming: Foundations and Principles |publisher=[[Francis & Taylor]] |year=2010 |isbn=978-0-8247-4099-3}}</ref>

In fact, Dijkstra's explanation of the logic behind the algorithm:{{sfn|Dijkstra|1959|p=270}} 
{{blockquote|'''Problem 2.''' Find the path of minimum total length between two given nodes {{mvar|P}} and {{mvar|Q}}.

We use the fact that, if {{mvar|R}} is a node on the minimal path from {{mvar|P}} to {{mvar|Q}}, knowledge of the latter implies the knowledge of the minimal path from {{mvar|P}} to {{mvar|R}}.}}
is a paraphrasing of [[Richard Bellman|Bellman's]] [[Bellman equation#Bellman's principle of optimality|Principle of Optimality]] in the context of the shortest path problem.