Dijkstra's Algorithm

About

This page is about Dijkstra's Algorithm, a famous path-finding algorithm!

Description

Dijkstra's algorithm finds the shortest path from a source node to another given node in a graph.

Application

It's used everywhere! Here's just a short list of where all it can be used:

• GPS Naviation (Google Maps)
• Route Planning (Computer Networks)
• Logistics
• Social Networks
• Robotics and AI
• Flight Paths

Implementation

Pseudocode

     1| def dijkstra(v):
     2|    pq = new PriorityQueue()
     3|    pq.insert([dest: v, pred: null, cost: 0])
     4|    while (!pq.isEmpty()):
     5|        [dest, pred, cost] = pq.removeMin()
     6|        if dest is unvisited:
     8|            mark dest visited
     9|            store pred and cost for dest
    10|            for weight (w) in edges to destination (u) neighbor:
    11|                pq.insert([u, dest, cost + w])

Runtime Complexity

Worst Case Runtime:

For more information, check out Wikipedia.