Understanding Weighted Graphs: Dijkstra's Algorithm Revealed
Have you ever wondered when navigating Google Maps how it comes up with the quickest route to your destination? The answer to your curiosity lies in the magnificent world of weighted graphs and Dijkstra's algorithm.
Let's explore this further. Imagine you're traveling on different roads of unequal lengths and different speed limits, thus affecting the time spent on each route. In graph theory, this scenario could symbolize a weighted graph where each edge (or path) carries its weight (the time spent on each road). Therefore, finding the quickest route essentially means figuring out the shortest path in this weighted graph, and here is where Dijkstra's algorithm comes to play. This article will walk you through a deep understanding of weighted graphs and the backbone of quickest route algorithms, Dijkstra's algorithm.
A Closer Look at Dijkstra's Algorithm
Let's explore the following weighted graph.
This graph shows two possible routes from the Origin to Destiny. The numbers represent the time it takes to move from one point to another. If you recall from our discussion on breadth-first search, it would suggest the shortest route as Origin -> A -> Destiny. While this path has fewer segments, the quickest option would be through Dijkstra's Algorithm, taking the path Origin -> B -> A -> Destiny, taking a total of 6 minutes.
Now that we know the result, let's break it down into four simple steps:
- You identify the cheapest node. This refers to the node reachable in the least amount of time.
- Update the costs of its neighboring nodes.
- Repeat the process for every node in the graph.
- Calculate the final path.
Step 1: Finding the Cheapest Node
| Vertex | Time |
|---|---|
| A | 6 |
| B | 2 |
| Destiny | Infinity |
You're at the Origin contemplating your next stop: Node A takes 6 minutes, while Node B takes 2 minutes. The time required to get to the Destiny is still unknown, hence we consider it infinite for now. Therefore, Node B becomes our cheapest node.
Step 2: Updating the Costs of the Neighbors
| Vertex | Time |
|---|---|
| A | |
| B | 2 |
| Destiny | 7 |
From Node B, you realize you could reach Node A in 5 minutes (2 to get to B then 3 to A) which is a minute less than going directly. Subsequently, you update the time for Node A. Similarly, you understand that reaching the Destiny would take 7 minutes (2 to B then 5 to Destiny).
Step 3 and 4: Repeat and Compute the Final Path
The process is then repeated for Node A and the final path calculated. The quickest route ends up being Origin -> B -> A -> Destiny, taking a total of 6 minutes.
| Vertex | Time |
|---|---|
| A | 5 |
| B | 2 |
| Destiny |
Digging into the Algorithm
In Dijkstra's Algorithm, each edge possesses an associated number known as the weight and the graph becomes known as a "weighted graph." Whereas previously in our breadth-first search, the "shortest path" referred to the minimum number of segments, in Dijkstra's interpretation, it implies the path with the least cumulative weight.
One caveat in Dijkstra's algorithm is its inefficiency in dealing with cycles. A cycle occurs when you can start at one vertex and traverse through the graph to return to the same vertex. Take a look at the following example:
Here, even though the quickest path is Origin -> A -> B -> Destiny taking 3 minutes, Dijkstra's algorithm may keep circling between A and B.
Handling Negative Weights
Dijkstra's algorithm fails to handle negative weights. In cases where there are negative weights, like this:
The quickest path would be Origin -> A -> B -> Destiny, taking 33 minutes. Using Dijkstra's algorithm, we would unusedly arrive at longer routes. Instead, for such cases, we use the Bellman-Ford algorithm, a more suitable algorithm for graphs involving negative weights. While Bellman-Ford isn't in the scope of this article, we'll surely approach it in possible future articles.
Implementing Dijkstra's Algorithm
Let's dive into creating Dijkstra's algorithm for our initial graph using JavaScript. Before implementing, you'll need three hash tables.
The first table will store the graph, the second table will store the costs, and the third table will store the parents. The cost and parents tables will be updated as the algorithm proceeds. Below you'll find a sample implementation of Dijkstra's algorithm.
First, let's implement the graph.
const graph = {}
graph['origin'] = {}
graph['origin']['a'] = 6
graph['origin']['b'] = 2
graph['a'] = {}
graph['a']['destiny'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['destiny'] = 5
graph['destiny'] = {} // The destination node has no neighbors
In order to get all the neighbors of a node, you can use the Object.keys() method.
Now, you need a hash table to store the weights.
const weights = {}
weights['a'] = 6
weights['b'] = 2
weights['destiny'] = Infinity // The time to reach the destination is unknown for now
And the last, but not least, you need a hash table to store the parents.
const parents = {}
parents['a'] = 'origin'
parents['b'] = 'origin'
parents['destiny'] = null // The destination has no parent yet
Finally, you need a way to keep track of all the processed vertices, as they don't need to be processed more than once.
const processed = new Map()
Now, with all the necessary data structures in place, you can implement the algorithm.
Conclusion
Diagramming the quickest route on Google Maps no longer feels like a giant enigma. In summary, Dijkstra's algorithm aids in navigating a weighted graph efficiently by finding the path with the least total weight. Remember, weighted graphs are your friend when you're trying to find the shortest route in terms of weight or cost, not necessarily the number of segments!
Have any more doubts about Dijkstra's Algorithm, weighted graphs, or any other algorithm? Feel free to reach out. You can also subscribe to my newsletter for updates about my latest articles and guides. Happy coding!