Dijkstra's algorithm

related topics
{math, number, function}
{line, north, south}
{@card@, make, design}
{rate, high, increase}
{city, large, area}
{system, computer, user}

Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959,[1][2] is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. An equivalent algorithm was developed by Edward F. Moore in 1957.[3]

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

Contents

Algorithm

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.

Description

Suppose you want to find the shortest path between two intersections on a city map, a starting point and a destination. The order is conceptually simple: to start, mark the distance to every intersection on the map with infinity. This is done not to imply there is an infinite distance, but to note that that intersection has not yet been visited. (Some variants of this method simply leave the intersection unlabeled.) Now, at each iteration, select a current intersection. For the first iteration the current intersection will be the starting point and the distance to it (the intersection's label) will be zero. For subsequent iterations (after the first) the current intersection will be the closest unvisited intersection to the starting point—this will be easy to find.

Full article ▸

related documents
Binary relation
E (mathematical constant)
Abstract interpretation
Pushdown automaton
Random variable
Algebraic structure
Linear combination
Axiom schema of replacement
Heine–Borel theorem
Euclidean algorithm
Glossary of topology
Presentation of a group
Ideal class group
Factorization
Linear independence
IEEE 754-1985
Sequence
Elliptic curve
Gaussian quadrature
Type theory
Natural transformation
Absolute convergence
Fuzzy logic
Galois theory
Partition (number theory)
Ultrafilter
Database normalization
Probability density function
Complex analysis
Euler characteristic