Dijkstras Single Source Shortest Path Algorithm
(New York City, New York, USA)
Dijkstra's single source shortest path algorithm is used in graphing. It is an adaptation of the breadth first search traversal algorithm for use on weighted (but non-negative edge) graphs in order to find the shortest path (by edge weight) from one node to another node, or frequently from one node to all other nodes.
Dijkstra's algorithm does this by implementing a priority queue (most often via a binary heap in array based representation, though can be made even faster using a fibonacci heap). It is an example of the Dynamic Programming method of algorithm design.
GPS systems and Google maps make use of dijkstra's algorithm and its heuristic-using-brother, A* search for route planning. Another common use of Dijkstra's Algorithm is in path finding for video games as well as object avoidance in robotics.
Let distance be an array of integers
For every vertex V:
distance[v] = infinity.
Let PQ be a priority queue
distance[start_node] = 0
while (PQ is not Empty())
let current = PQ.top()
for every adjacent node u of current:
if distance[current] > distance[current] + u.weight
distance[current] = distance[current] + u.weight
At the completion of the algorithm, the distance array will have the distance from the start node to each indexed vertex.
Click here to post comments
Join in and write your own page! It's easy to do. How? Simply click here to return to Your algorithms.