Dijkstra's algorithm: Difference between revisions

Revision as of 21:41, 20 February 2004

Revision as of 18:37, 29 February 2004

Line 3:

<b>Dijkstra's algorithm</b>, named after its inventor the Dutch [[computer scientist]] [[Edsger Dijkstra]], solves a [[shortest path problem]] for a directed and connected [[graph theory|graph]] G(V,E) which has nonnegative (>=0) [[edge]] weights. The set V is the set of all [[vertex|vertices]] in the graph G. The set E is the set of ordered pairs which represent connected vertices 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, &infin;)] 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).

Line 32:

1 Initialize-Single-Source(G,s)

2 S := empty set

3 Q := set of all vertexesvertices

4 '''while''' Q is not an empty set

5 '''do''' u := Extract-Min(Q)

Line 58:

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.