Dijkstra's algorithm: Difference between revisions

Revision as of 09:51, 3 May 2004

Revision as of 18:26, 6 May 2004

Line 2:

[[pl:algorytm Dijkstry]]

'''Dijkstra's [[algorithm]]''', named after its inventor the Dutch [[computer science|computer scientist]] [[Edsger Dijkstra]], solves the [[shortest path problem]] for a directed [[graph theory(mathematics)|graph]] with nonnegative [[edge (graph theory)|edge]] weights.

For example, if the vertices of the graph represent cities and edge weights

represent driving distances between pairs of cities connected by a direct road,

Dijkstra's algorithm can be used to find the shortest route between two cities.

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 [[vertex (graph theory)||vertices]] in the graph ''G''. Each [[edge (graph theory)|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''.