Dijkstra's algorithm is an algorithm which is used to find the shortest path in a graph with weighted edges. In this article, we'll introduce the algorithm, discuss a high level implementation, and show a full code implementation in multiple languages. If you'd like to skip to the code, feel free to jump to the bottom.
Dijkstra's Algorithm
Dijkstra's algorithm is an algorithm which finds the shortest possible path between two vertices in a graph with weighted edges. In this article, we'll use the terms vertex and node synonomously. In the most common implementation, this algorithm actually finds the shortest paths between a start node and all other nodes. This algorithm is useful in situations such as:
- Find the fastest route between two cities.
- Determine the cheapest way to nagivate from one point to another.
- Determining degrees of seperation between friends in a social network.
Some applications may require functionality on top of Dijkstra's algorithm to fully implement.
High Level Algorithm
This algorithm is implemented using three main parts:
- A map object shortestPaths which maps nodes to the shortest path's cost from the start node to that node (so far).
- A map object prevNodes which maps nodes to its previous node in its shortest path (so far).
- A breadth-first search, starting from the start node.
At the beginning, shortestPaths will have one entry which maps the start node to 0. This is done for convenience, and does make sense because the weight to travel from the start node to itself is 0, since we're already there. As the breadth first search proceeds, the shortest path for each node will be set initially to the first path which finds it, then will be updated if another node also touches that node, and that path has a lower cost. At the end, the shortestPaths object will contain all shortest paths from the start node to each other node, and prevNodes will contain all immediate previous nodes for each node in its shortest path. The full algorithm can be described as:
- Create a map shortestPaths and add an entry in shortestPaths to map the start node to 0.
- Create a map prevNodes.
- Create a queue nodesQueue to store nodes which have been discovered but not yet visited.
- Create a set visitedNodes to keep track of nodes which have been visited.
- Create a variable currentNode and set to the start node.
- While the queue is not empty:
- Add currentNode to visitedNodes.
- Create a variable dist, get the value mapped to currentNode in shortestPaths, and assign to dist.
- For each outgoing node of currentNode:
- If the child node has not been visited, add to nodesQueue.
- Create a variable childDist and assign to it: dist + weight of the edge from currentNode to the child node.
- Check if prevNodes has the child node.
- If it does, and dist is less than the current best path, set shortestPaths->[child node] to dist and prevNodes->[child node] to currentNode.
- If it does not, set shortestPaths->[child node] to dist and prevNodes->[child node] to currentNode.
- Dequeue from nodesQueue and assign to currentNode.
Once all nodes have been visited, shortestPaths will have all of the shortest paths from the start node to each other node. We can reconstruct the path itself with a loop starting from the end node: create an empty array for the path, add the current node (starting with the end node) to the path, get the previous node of the current node, and set the current node to that node. When we reach the start node, the path is complete (but in reverse order).
Space and Time Complexity
The time complexity is determined by two variables: the number of nodes in the graph and the number of edges between nodes. Graphs with many nodes but few edges will take less steps than graphs with many nodes and many edges.
Complexity | Notes | |
---|---|---|
Space | O(n) | The algorithm uses two maps, each with n entries. |
Time | O(n + e) | This uses two variables: n represents the number of nodes, and e represents the number of edges in the graph. |
Directed Graphs
In our description and implementation below, we are finding the shortest path on an undirected graph, which means we can traverse each edge in either direction. Dijkstra's algorithm also works on directed graphs, which allows for connections between nodes to have different weights based on the direction, and allows some nodes to only connect to others in one direction. To support this, we don't need to change Dijkstra's algorithm at all, just the way we represent graph nodes.
Full Implementation
In the implementation below, we've created two helper classes: GraphNode and ShortestPath. GraphNode encapsulates a vertex with a string value and outgoing connections to other vertices with weights. ShortestPath encapsulates a solution: an array of nodes corresponding to the shortest path and the sum of weights over that path.