The Pathfinder Graph Algorithm in Python

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 Path Finder Algorithm

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 length 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!

Where to Go From Here?

Enough theory, let’s get some practice!

To become successful in coding, you need to get out there and solve real problems for real people. That’s how you can become a six-figure earner easily. And 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?

Practice projects is how you sharpen your saw in coding!

Do you want to become a code master by focusing on practical code projects that actually earn you money and solve problems for people?

Then become 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.

Join my free webinar “How to Build Your High-Income Skill Python” and watch how I grew my coding business online and how you can, too—from the comfort of your own home.

Join the free webinar now!

Leave a Comment