Dijkstra's algorithm: Difference between revisions

Revision as of 04:39, 1 June 2002

Revision as of 13:20, 1 June 2002

Line 1:

<b>Disjkstra's algorithm</b> 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|vertexesvertices]] 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,oo) 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.