Dijkstra's Algorithm for SSSP

Let G be a directed graph, s a node of G, and cost a cost function on the edges of G. A single source shortest path algorithm computes the shortest paths from s to all other nodes of G with respect to cost.

Remark: Finding the shortest path from one node to one other node is not significantly faster than computing the shortest paths from the source to all other nodes.

DIJKSTRA_T() is the LEDA function for computing single source shortest paths in a directed graph with non-negative edge costs. DIJKSTRA_T() is a template function. The template parameter NT can be instantiated with any number type.

Example of How to Use DIJKSTRA_T()

DIJKSTRA() is the name of the preinstantiated versions of DIJKSTRA_T(). There is one function DIJKSTRA() for edge costs of type int and one for double.

Example of How to Use DIJKSTRA()

Important Notice: DIJKSTRA() only performs correctly if all arithmetic is performed without rounding errors and without overflows. If you are not sure about this, you should use DIJKSTRA_T() with one of the LEDA number types.

Running time

The running time of DIJKSTRA_T() and DIJKSTRA() for a graph G=(V,E) is O(|E|+|V|log|V|) .

Tips

• If your edge costs are non-negative, you can call for DIJKSTRA_T() SSSP.
• If you know that there can be no overflows and no rounding errors you can use DIJKSTRA().
• The Generic Algorithms for SSSP provide a convenient interface to all SSSP algorithms in LEDA. You do not have to think about cycles and negative edge costs beforehand.
• If your graph is acyclic, you can also use SSSP Algorithm for Acyclic Graphs.
• If your graph contains cycles and there are edges with negative costs, you can also call the Bellman-Ford Algorithm for SSSP.
• LEDA also provides functions for checking the results of an SSSP Algorithm.

See also:

Shortest Path Algorithms

Checking the Results of an SSSP Algorithm

Generic Algorithms for SSSP

SSSP Algorithm for Acyclic Graphs

Bellman-Ford Algorithm for SSSP

Number Types

Graphs and Related Data Types

Graph Algorithms

Manual Entries:

Manual Page Shortest Path Algorithms