Dijkstra's algorithm: Difference between revisions

Revision as of 05:32, 6 January 2003

Revision as of 05:44, 6 January 2003

Line 2:

<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 vertexes in the graph (if (u,v) belongs to E then vertexes u and v are connected).

Assume that the function w: V x V -> [0,&infin; infinity) 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.) For a given vertex s in V, the algorithm computes the shortest path (lowest total value of w) from s to any other vertex t.

A few subroutines for use with Dijkstra's algorithm: