**Dijkstra's algorithm**, named after its inventor the Dutch computer scientist Edsger Dijkstra, solves a shortest path problem for a directed and connected graph G(V,E) which has nonnegative (>=0) edge weights. The set V is the set of all vertices in the graph G. The set E is the set of ordered pairs which represent connected vertexes in the graph (if (u,v) belongs to E then there is a connection from vertex u to vertex v).

Assume that the function w: V x V -> [0, ∞] describes the cost w(x,y) of moving from vertex x to vertex y (non-negative cost). (We can define the cost to be infinite for pairs of vertices that are not connected by an edge.) The cost of a path between two vertices is the sum of costs of the edges in that path. The cost of an edge can be thought of as (a generalisation of) the distance between those two vertices. For a given pair of vertices s,t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path).

The algorithm works by constructing a subgraph S of such that the distance of any vertex v' (in S) from s is **known** to be a minimum within G. Initially S is simply the single vertex s, and the distance of s from itself is known to be zero. Edges are added to S at each stage by (a) identifying all the edges e_{i} = (v_{i1},v_{i2}) in G-S such that v_{i1} is in S and v_{i2} is in G, and then (b) choosing the edge e_{j} = (v_{j1},v_{j2}) in G-S which gives the minimum distance of its vertex v_{j2} (in G) from s from all edges e_{i}. The algorithm terminates either when S becomes a spanning tree of G, or when all the vertices of interest are within S.

The procedure for adding an edge e_{j} to S maintains the property that the distances of all the vertices within S from s are **known** to be minimum.

A few subroutines for use with Dijkstra's algorithm:

Initialize-Single-Source(G,s)

1Relax(u,v,w)foreach vertex v in V[G] 2dod[v] := infinite 3 previous[v] := 0 4 d[s] := 0

1v = Extract-Min(Q) searches for the vertex v in the vertex set Q that has the least d[v] value. That vertex is removed from the set Q and then returned.ifd[v] > d[u] + w(u,v) 2thend[v] := d[u] + w(u,v) 3 previous[v] := u

The algorithm:

Dijkstra(G,w,s)

1 Initialize-Single-Source(G,s) 2 S := empty set 3 Q := set of all vertexes 4Dijkstra's algorithm can be implemented efficiently by storing the graph in the form of adjacency lists and using a heap as priority queue to implement the Extract-Min function. If the graph haswhileQ is not an empty set 5dou := Extract-Min(Q) 6 S := S union {u} 7foreach vertex v which is a neighbour of u 8doRelax(u,v,w)

If we are only interested in a shortest path between vertexes s and t, we can terminate the search at line 5 if u == t.

Now we can read the shortest path from s to t by iteration:

1 S = empty sequence 2 u := t 3 S = u + S /* insert u to the beginning of S */ 4Now sequence S has the shortest path from s to t.ifu == s 5 end 6 u = previous[u] 7 goto 3

OSPF Open shortest path first is a well known real world implementation used in internet routing.

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-hard, so it can't be solved by Dijkstra's algorithm, nor by any other known, polynomial-time algorithm.

- Cormen, Leiserson, Rivest:
*Introduction to Algorithms*