In the ending of the previous article, we said that breadth-first search can be modified to obtain completely different behaviours. Today, we are going to see how exactly we can modify BFS to obtain a brand new algorithm. Firstly though, we need to introduce the weighted graph notion. This is the last articles in this mini series, Why is Graph Theory so amazing?, as next week we're going to explore another interesting computing subject!
Weighted Graphs
A weighted graph is a graph in which each edge has an attached weight (or cost) to it.
For example, the graph above, let it be called G, represents a weighted graph: the edge (2, 5) has weight 10, the edge (1,3) has weight 15, and so on.
From a practical standpoint, a weighted graph can mean a network of roads, with each edge cost representing the distance between two cities, or, when working with live data, a sort of time coefficient that can be affected by traffic events - accidents, maintenance work, and so on.
Now, we can ask the following question: how can we go from a node i to a node j with minimal cost?
Computing The Shortest Path
One popular algorithm to compute the shortest path from a node to another is called Dijkstra's Algorithm, after the Dutch computer scientist (among other things), Edsger Wybe Dijkstra. In an interview given in 2001, Dijkstra said that the algorithm was designed without pen & paper, while sitting in cafe with his fiance.
The algorithm follows a pretty simplistic and elegant approach. We can consider it a sibling of breadth first search, of which I gave a more detailed overview in this article. The main difference is the order in which the algorithm visits the nodes: instead of expanding nodes in the order in which they were put in the queue, in a First-In, First-Out manner, the algorithm remembers, for each node, the cost with which it has been reached, expanding nodes reached with a lower cost first.
Let the starting node be called start, and the node to which we want to find the cost be called finish. Let cost be an array which contains the cost to reach each of the N nodes in our graph. Formally, the algorithm should follow the next steps:
- mark all nodes as unvisited; moreover, mark the cost of node start with 0 and the cost to get to any other node with a very high value; put start in the queue.
- while there are nodes left in the queue, and we haven't found a cost for the finish node:
- pop a node from the queue, let it be called u.
- if the node has already been visited (i. e., we could get to it from multiple directions, so we put it in the queue multiple times, with different costs), there is no need to visit it again, as we have already expanded the best way to reach it; continue the algorithm.
- if the node hasn't already been visited, search through its neighbours; for any neighbour i, we check whether coming from u can improve its respective cost (i. e., if the current cost to get to i is greater than the cost to get to u plus the cost of the edge (u, i); if so, put i in the queue, with the associated cost.
- after looking at all the neighbours of u, mark u as visited, and go back to 2..
Now, let us work towards an implementation of Dijkstra's algorithm.
Representing Weighted Graphs in Memory
You may remember the adjacency_list.py file we wrote for the first article. In order for that graph "wrapping" to handle weighted graphs, we need to modify two fundamental things in its structure:
- For a node i, every entry in its neighbour list should now remember a tuple: the node which it leads to and the cost of the edge.
- The is_valid_tuple function, which we used for checking user input, should be modified to only check the first two elements of the tuple to be nodes; specifically, this line should be modified:
The length of the tuple should be modified to 3, and, as you can see, we used the Python built-in all() function to check for the nodes. We can modify our iterable, x, to only return the first two elements, by changing it to x[0:2]. This Python syntax is called extended slicing. When using it like [start:stop], it returns an iterable object containing elements from index start to index stop-1 of the iterable on which we applied the syntax. Finally, our line will become:
One other thing we have to keep into account is the way in which we extract the result of our lowest-cost path yet, in each step of the algorithm (we consider a graph G with N nodes):
- We can use a regular array to construct the queue of our candidates, and look through all its entries every time - that's N entries, for each candidate in our shortest path.
- We can optimise the runtime by using an appropiate data structure: a binary heap, with logarithmic minimum extraction and insertion - doing roughly log(N) operations for each shortest path candidate.
Luckily, the Python library contains a PriorityQueue collection, which satisfies our needs for implementing the faster Dijkstra variant, if we are not too interested in implementing a data structure such as this ourselves.
The algorithm I have described below only provides us with the cost of the path, but not with the path itself. However, we can compute it quite simply if, each time we computed a better candidate for a path cost, we would remember the "parent" node, the node which we expanded to get there, in addition to the cost itself. Then, we can use recursion to go from "parent" to "parent", and print the nodes we encounter after making the recursive calls.
Below is the modified version of the graph wrapping, and the implementation of the algorithm:
The snippet outputs the smallest path cost as 7, with the route 1 -> 4 -> 3 when we want to compute the cost between 1 and 3.
Looking at the graph, we can see that this is indeed the answer.
Conclusion
This week's article ends here. This is the last entry in this mini-series, Why is Graph Theory so amazing?, during which I hope I offered a somewhat clear image on what graphs are and some fun ways to use them. Unfortunately, the subject is too broad to be treated in just a series of articles.
Next week, we're gonna present a completely new aspect of Computer Science. Until then, you can pass the time by reading another article in the series!
Top comments (1)
laic