Dijkstras Single Source Shortest Path Algorithm

by Max
(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.

Pseudocode:

Let distance be an array of integers
For every vertex V:
    distance[v] = infinity.

Let PQ be a priority queue
    PQ.push(start_node, 0)
    distance[start_node] = 0

while (PQ is not Empty())
Do
    let current = PQ.top()
    for every adjacent node u of current:
    if distance[current] > distance[current] + u.weight
        distance[current] = distance[current] + u.weight
        PQ.push(u, distance[current]);


At the completion of the algorithm, the distance array will have the distance from the start node to each indexed vertex.