
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 singlesource 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 ISIS 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 7541985 
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 
