Knowing the basics is what sets apart the great from the intermediate coders.
In other words, a simple and effective way to grow your skills is to learn the basics of computer science.
Python Pathfinder Algorithm
In this tutorial, you’ll learn about the pathfinder algorithm that recursively determines whether there’s a direct or indirect path between two vertices in the graph.
For example, in the graphic, is there a path from vertex 4 to vertex 1? What about a path from vertex 3 to vertex 4?
Here’s the code that solves the pathfinder problem in Python:
# The graph represented as adjancy matrix
# See https://en.wikipedia.org/wiki/Adjacency_matrix
G = [[1,1,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,1,1,1,0],
[1,0,0,1,1]]
n = len(G) # The number of vertices in the graph
# Is there a path from vertex i to vertex j?
def find_path(i, j, path_length):
# The maximal length of a path without a cycle is n
# (traverse each vertex once)
if path_length>n:
return False
# Is there a direct path from i to j?
if G[i][j]==1:
return True
# Is there an indirect path from i to j over i's neighbor k?
for k in range(n):
if G[i][k]==1: # Vertex k is a neighbor of i
if find_path(k, j, path_length+1):
return True
# We have not found any path
return False
# Path from vertex 1 to vertex 1?
print(find_path(1, 1, 0))
# Path from vertex 4 to vertex 1?
print(find_path(4, 1, 0))
Take a guess… what’s the output of this code snippet?
A fundamental area of computer science is graph theory.
Of course, you could solve the code snippet without even knowing about graph theory.
After all, this is what your computer does when running this code. But the computer does not have to code—people do.
So let us dive into graph theory via an ultra quick crash course.
What is a Graph?
So what is a graph?
A graph is a complex data structure such as a list, a set, or a dictionary. The data structure is complex not because you can not understand it but because it consists of other data structures.
You use the graph data structure if you want to represent relations between data items.
We denote the relations as edges and the data items as vertices.
An example is the Facebook social graph. Facebook represents users as vertices and friendship relations as edges. Two users are connected via an edge in the graph if they are (Facebook) friends.
Adjacency Matrix
How does the data structure look like?
In the puzzle, we use an adjacency matrix as graph data structure G. Each row i in the matrix stores the out-neighbors of vertex i. Each column j stores the in-neighbors of vertex j.
Thus, if we want to know whether there is an edge from vertex i to vertex j, we check whether G[i][j]==1.
Pathfinder Algorithm Explained
How do we check whether there is a path between two vertices?
The function findPath(i, j, pathLength) checks whether there is a direct or indirect path between two vertices i and j.
We know that there is a direct path between vertices i and j if they are already neighbors, i.e., G[i][j]==1. To determine whether there is an indirect path, the idea is to use a recursive approach. There is an indirect path, if a vertex k exists such that there is a path i --> ... --> k --> ... --> j.
The variable pathLength stores the length of the current path. We increment it in each recursion level as the current path length increases by one.
Note that all paths with length >n consist of more than n vertices. In other words, at least one vertex is visited twice and a cycle exists in this recursion instance.
Hence, we skip recursion for paths with lengths greater than the number of vertices in the graph.
This puzzle asks whether there is a path between 3 and 0.
If you understand what the code is doing, it suffices to look at the adjacency matrix G. There is a direct path from vertex 3 to vertices 1 and 2 (and to itself).
But both vertices 1 and 2 have no out-neighbors. Therefore, there is no such path from 3 to any other vertex (besides vertices 1 and 2).
Related Video
Pathfinder Python Interactive Shell
You can try the algorithm yourself in our interactive code shell:
Exercise: Change the adjacency matrix so that there exists an indirect path from vertex 0 to vertex 4!
Academy Course – Mastering the Top 10 Graph Algorithms
If you want to improve your fundamental computer science skills, there’s nothing more effective than studying algorithms.
To help you master the most important graph algorithms, we’ve just launched the “Top 10 Algorithms” course at the Finxter Computer Science Academy. This great course from Finxter Star Creator Matija ⭐ teaches you the most important graph algorithms such as BFS, DFS, A*, and Dijkstra.
Understanding these algorithms will not only make you a better coder, but it’ll also lay a strong foundation on which you can build your whole career as a computer scientist.
Click the screenshot to find out more:
Where to Go From Here?
Enough theory. Let’s get some practice!
Coders get paid six figures and more because they can solve problems more effectively using machine intelligence and automation.
To become more successful in coding, solve more real problems for real people. That’s how you polish the skills you really need in practice. After all, what’s the use of learning theory that nobody ever needs?
You build high-value coding skills by working on practical coding projects!
Do you want to stop learning with toy projects and focus on practical code projects that earn you money and solve real problems for people?
🚀 If your answer is YES!, consider becoming a Python freelance developer! It’s the best way of approaching the task of improving your Python skills—even if you are a complete beginner.
If you just want to learn about the freelancing opportunity, feel free to watch my free webinar “How to Build Your High-Income Skill Python” and learn how I grew my coding business online and how you can, too—from the comfort of your own home.