Dijkstra's algorithm
In plain wordsA classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next.
An algorithm that computes shortest paths from a source node to all other nodes of a graph with non-negative edge weights. It keeps tentative distances, initially zero for the source and infinite elsewhere, and repeatedly settles the unsettled node with the smallest tentative distance, relaxing each of its outgoing edges — lowering a neighbor's tentative distance if the route through the settled node is shorter. Because weights are non-negative, a node's distance is final once it is settled. With a binary heap it runs in O((V + E) log V) time, and with a Fibonacci heap in O(E + V log V). In AI it is the uninformed special case of A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first. with a zero heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., called uniform-cost search; it also underlies route planning, link-state network routing such as OSPF, and robot path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.. Graphs with negative edge weights need other methods, such as the Bellman–Ford algorithm.
Origin
Devised by the Dutch computer scientist Edsger W. Dijkstra in 1956, by his own account in about twenty minutes at an Amsterdam café, to demonstrate the ARMAC computer; he published it in 1959 in 'A Note on Two Problems in Connexion with Graphs' (Numerische Mathematik).
Related
- A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
- breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first.
- best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next.
- path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added.
Sources
- Dijkstra, E. W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269–271.
Mentioned in
traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added.