# Dijkstra`s Algorithm

**Dijkstra’s algorithm**, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959,is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path algorithm is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

Dijkstra’s original algorithm does not use a min-priority queue and runs in time (where is the number of vertices). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in (where is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

Note that graphs under special cases such as integer and/or bounded weights, can be improved further in complexity. See the following section on running time.

## Algorithm

Let the node at which we are starting be called the **initial node**. Let the **distance of node Y** be the distance from the

**initial node**to

*Y*. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the
*unvisited set*consisting of all the nodes. - For the current node, consider all of its unvisited neighbors and calculate their
*tentative*distances. Compare the newly calculated*tentative*distance to the current assigned value and assign the smaller one. For example, if the current node*A*is marked with a distance of 6, and the edge connecting it with a neighbor*B*has length 2, then the distance to*B*(through*A*) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. - When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the
*unvisited set*. A visited node will never be checked again. - If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the
*unvisited set*is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished. - Select the unvisited node that is marked with the smallest tentative distance, and set it as the new “current node” then go back to step 3.

## Pseudocode

In the following algorithm, the code `u := vertex in `

, searches for the vertex *Q* with min dist[u]

in the vertex set `u`

that has the least `Q``dist[`

value. `u`]`length(`

returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes `u`, `v`)

and `u`

. The variable `v`

on line 17 is the length of the path from the root node to the neighbor node `alt`

if it were to go through `v`

. If this path is shorter than the current shortest path recorded for `u`

, that current path is replaced with this `v`

path. The `alt``previous`

array is populated with a pointer to the “next-hop” node on the source graph to get the shortest route to the source.

1functionDijkstra(Graph,source): 2 dist[source] := 0// Distance from source to source3for eachvertexvinGraph:// Initializations4ifv≠source5 dist[v] := infinity// Unknown distance function from source to v6 previous[v] := undefined// Previous node in optimal path from source7end if8 addvtoQ// All nodes initially in Q (unvisited nodes)9end for10 11whileQis notempty:// The main loop12u:= vertex inQwith min dist[u]// Source node in first case13 removeufromQ14 15for eachneighborvofu:// where v has not yet been removed from Q.16alt:= dist[u] + length(u,v) 17ifalt< dist[v]:// A shorter path to v has been found18 dist[v] :=alt19 previous[v] :=u20end if21end for22end while23returndist[], previous[] 24end function

If we are only interested in a shortest path between vertices

and `source`

, we can terminate the search at line 13 if `target`

. Now we can read the shortest path from `u` = `target`

to `source`

by reverse iteration:`target`

1S:= empty sequence 2u:=target3whileprevious[u] is defined:// Construct the shortest path with a stack S4 insertuat the beginning ofS// Push the vertex into the stack5u:= previous[u]// Traverse from target to source6end while

Now sequence

is the list of vertices constituting one of the shortest paths from `S`

to `source`

, or the empty sequence if no path exists.`target`

A more general problem would be to find all the shortest paths between

and `source`

(there might be several different ones of the same length). Then instead of storing only a single node in each entry of `target``previous[]`

we would store all nodes satisfying the relaxation condition. For example, if both

and `r`

connect to `source`

and both of them lie on different shortest paths through `target`

(because the edge cost is the same in both cases), then we would add both `target`

and `r`

to `source``previous[`

. When the algorithm completes, `target`]`previous[]`

data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these shortest paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.

## Running time

An upper bound of the running time of Dijkstra’s algorithm on a graph with edges and vertices can be expressed as a function of and using big-O notation.

For any implementation of vertex set the running time is in , where and are times needed to perform decrease key and extract minimum operations in set , respectively.

The simplest implementation of the Dijkstra’s algorithm stores vertices of set in an ordinary linked list or array, and extract minimum from is simply a linear search through all vertices in . In this case, the running time is .

For sparse graphs, that is, graphs with far fewer than edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a self-balancing binary search tree or binary heap, the algorithm requires time (which is dominated by , assuming the graph is connected). To avoid look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap’s index (and keep it up to date as priority queue changes), making it take only time instead. The Fibonacci heap improves this to .

Various special cases can indeed be improved further.

When arc weights are integers and bounded by a constant *C*, the usage of a special priority queue structure by Van Emde Boas etal.(1977) (Ahuja et al. 1990) brings the complexity to . Another interesting implementation based on a combination of a new Radix-heap and the well-known Fibonacci-heap runs in complexity (Ahuja et al. 1990). Finally, the best algorithms in this special case are as follows. The algorithm given by (Thorup 2000) runs in time and the algorithm given by (Raman 1997) runs in time.

Also, for directed acyclic graphs, it is possible to find shortest paths from a given starting vertex in linear time, by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum length obtained via any of its incoming edges.^{[4]} ^{[5]}

In the special case of integer weights and undirected graphs, the Dijkstra’s algorithm can be completely countered with a linear complexity algorithm