Dijkstra's algorithm finds the shortest path from a source node to every other node. It can be used to find the shortest path to a specific destination node by early termination.
The algorithm uses a min-priority queue data structure for selecting the shortest paths known so far. The most common implementation has time complexity O(n+mlogm)
Dijkstra's algorithm is a greedy algorithm. What does this mean?
A greedy algorithm is an algorithm that makes locally optimal choices at each step with the hope of finding a global optimum solution.
Other examples include: Kruskal's algorithm, The Travelling Salesman Problem
Dijkstra's algorithm is more efficient than others such as Bellman Ford when it comes to large graphs. However, the algorithm requires no negative weight edges.
- extensively used in route planning and navigation systems
- can find the shortest path between locations
- enable route guidance for drivers, pedestrians and transport networks
- e.g Google maps uses Dijkstra combined with the A* algorithm!
Distance to the start node = 0
Distance to every other node = (infinity)
All nodes marked as unvisited
(Can store a previous node for each node to remember paths)
Choose the current node: pick the unvisited node with smallest known distance
Update neighbouring nodes: if the new distance is smaller then update it
Mark the current node as visited (shortest path now final)
Repeat until all nodes visited.