Dijkstra's algorithm

The input of the algorithm consist of a weighted directed graph G and a source vertex s in G. We will denote V the set of all vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. Set of all edges is denoted E. Weights of edges are given by a weight function w: E -> [0, ∞]; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as (a generalisation of) the distance between those two vertices.

The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.

Table of contents

1 Description of the algorithm 2 Pseudocode 3 Running time 4 Related problems and algorithms 5 References 6 External links

Description of the algorithm

The algorithm works by keeping for each vertex v the cost d[v] of the shortest path found so far. Initially, this value is 0 for the source vertex s and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices. When the algorithm finishes, d[v] will be the cost of the shortest path from s to v or infinity, if no such path exists.

The basic operation of Dijkstra's algorithm is edge relaxation: if there is an edge from u to v, then the shortest known path from s to u can be extended to a path from s to v by adding edge (u,v) at the end. This path will have length d[u]+w(u,v). If this is less than d[v], we can replace current value of d[v] with the new value.

Edge relaxation is applied until all values d[v] represent the cost of the shortest path from s to v. The algorithm is organized so that each edge (u,v) is relaxed only once, when d[u] has reached its final value.

The algorithm maintains two sets of vertices S and Q. Set S contains all vertices for which we know that the value d[v] is already the cost of the shortest path and set Q contains all other vertices. Set S starts empty, and in each step one vertex is moved from Q to S. This vertex is chosen as the vertex with lowest value of d[u]. When a vertex u is moved to S, the algorithm relaxes every outgoing edge (u,v).

Pseudocode

In the following algorithm, u := Extract-Min(Q) searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and then returned.

Dijkstra(G,w,s)

1  for each vertex v in V[G]                        // Initialization
2     do d[v] = infinity
3        previous[v] = undefined
4  d[s] = 0
5  S = empty set
6  Q = set of all vertices
7  while Q is not an empty set
8     do u = Extract-Min(Q)
9        S = S union {u}
10       for each edge (u,v) outgoing from u
11           do if d[v] > d[u] + w(u,v)             // Relax (u,v)
12                 then d[v] = d[u] + w(u,v)
13                      previous[v] = u

1 S = empty sequence 
2 u = t
3 while defined u                                        
4    do insert u to the beginning of S
5       u = previous[u]

Running time

We can express the running time of Dijkstra's algorithm on a graph with m edges and n vertices as a function of m and n using the Big O notation.

The simplest implementation of the Dijkstra's algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is Θ(n²).

For sparse graphs, that is, graphs with much less than n² edges, Dijkstra's algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a Fibonacci heap as priority queue to implement the Extract-Min function. The algorithm's time requirements are Θ(m + n log n).

Related problems and algorithms

Unlike Dijkstra's algorithm, Bellman-Ford algorithm can be used on the graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.

A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. That problem is NP-complete, so it can't be solved by Dijkstra's algorithm, nor by any other known, polynomial-time algorithm.

References

• Animation of Dijkstra's algorithm