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.
Some applications may require functionality on top of Dijkstra's algorithm to fully implement.
High Level Algorithm
- 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.
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.
|Space||The algorithm uses two maps, each with n entries.|
|Time||This uses two variables: n represents the number of nodes, and e represents the number of edges in the graph.|
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.
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.