Python breadth-first search matrix print path

Question

I have this line of code that tests wether or not there is a path to be found in a labyrinth represented by a matrix. How do I print the path at the end after I've determined wether or not there is a path. I've tried doing a stack but I'm not sure how to proceed.

from queue import Queue
maze=open(input())
matrix=maze.readlines()
matrix=[i.strip() for i in matrix]
matrix=[i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])
q=Queue()
row=0
col=0
q.put((row,col))
while not q.empty():
    row, col = q.get()
    if col+1 < numcols and matrix[row][col+1] == "0":
         q.put((row, col+1))
         matrix[row][col+1] = "2"
    if row+1 < numrows and matrix[row+1][col] == "0":
         q.put((row+1, col))
         matrix[row+1][col] = "3"
    if 0 <= col-1 and matrix[row][col-1] == "0":
         q.put((row, col-1))
         matrix[row][col-1] = "4"
    if 0 <= row-1 and matrix[row-1][col] == "0":
         q.put((row-1, col))
         matrix[row-1][col] = "5" 
row,col=numrows-1,numcols-1
var=matrix[row][col]
if var=="0":
    print ("There is no path.")
else:
    print ("There is a path.")

Here is a sample matrix:

0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0

Possible duplicate of [How does a Breadth-First Search work when looking for Shortest Path?](https://stackoverflow.com/questions/8379785/how-does-a-breadth-first-search-work-when-looking-for-shortest-path) — Nir Alfasi, Nov 08 '17 at 11:03
@PM2Ring This is a breadth first search, it does find the shortest path. — Arne, Nov 08 '17 at 11:11
@ArneRecknagel Thanks for that info. It's been a long time since I studied graph theory. ;) — PM 2Ring, Nov 08 '17 at 11:24
@PM2Ring To be clear, and because I didn't include it in the first comment, BFS finds the shortest path *in this case*, because the edges are unweighted. Most discussions about BFS will shortly introduce Dijkstra as a variant that will find the shortest path in a general setting, which is why it may appear that basic BFS can never find it on its own. — Arne, Nov 08 '17 at 11:30

程名锐 · Answer 1 · 2017-11-08T11:24:22.110

Because you are using BFS to find the path, the final approach cannot be the shortest path from the start point to the finish point, and actually, you can only get the result that which point is connected to the start point.

So, to get an exact path, you may use DFS to find a path and use a stack to save the points visited or use Dijkstra to find the shortest path from the start point to the finish point.

Here is a simple DFS function which uses recursion and the path is represented in character 2

suc = 0

def dfs(row, col):
    global suc
    if suc == 1:
        return
    matrix[row][col] = "2"

    if (row, col) == (numrows - 1, numcols - 1):
        print("Success")
        suc = 1

    if col + 1 < numcols and matrix[row][col + 1] == "0":
        dfs(row, col + 1)

    if row + 1 < numrows and matrix[row + 1][col] == "0":
        dfs(row + 1, col)

    if 0 <= col - 1 and matrix[row][col - 1] == "0":
        dfs(row, col - 1)

    if 0 <= row - 1 and matrix[row - 1][col] == "0":
        dfs(row - 1, col)


maze = open(input())
matrix = maze.readlines()
matrix = [i.strip() for i in matrix]
matrix = [i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])

dfs(0, 0)

var = matrix[numrows - 1][numcols - 1]

for m in matrix:
    print(m)

if var == "0":
    print("There is no path.")
else:
    print("There is a path.")

BFS does, in a maze with uniform edge weights as I assume is the case in this problem, find the shortest path. — Arne, Nov 08 '17 at 11:14

PM 2Ring · Answer 2 · 2017-11-08T11:33:49.780

Here's a fairly simple way to find the path, by tracing it backwards from the exit. You can reverse this by saving the moves to a stack.

To make it easier to see, I've changed your code slightly to put N, S, E, W in the matrix (for North, South, East, West). To decode those direction letters to (row, column) steps I use a dictionary.

from queue import Queue

maze='''\
0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0
'''

def show(matrix):
    for line in matrix:
        print(*line)
    print()

matrix=maze.splitlines()
matrix=[i.strip() for i in matrix]
matrix=[i.split() for i in matrix]
numrows, numcols = len(matrix), len(matrix[0])

show(matrix)

q=Queue()
row=0
col=0
q.put((row,col))
while not q.empty():
    row, col = q.get()
    if col+1 < numcols and matrix[row][col+1] == "0":
         q.put((row, col+1))
         matrix[row][col+1] = "W"
    if row+1 < numrows and matrix[row+1][col] == "0":
         q.put((row+1, col))
         matrix[row+1][col] = "N"
    if 0 <= col-1 and matrix[row][col-1] == "0":
         q.put((row, col-1))
         matrix[row][col-1] = "E"
    if 0 <= row-1 and matrix[row-1][col] == "0":
         q.put((row-1, col))
         matrix[row-1][col] = "S" 
row,col=numrows-1,numcols-1
var=matrix[row][col]

show(matrix)

if var=="0":
    print ("There is no path.")
    exit()
else:
    print ("There is a path.")

# Trace the path
step = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}
while True:
    print((row, col), 'go', var)
    if row == 0 and col == 0:
        break
    r, c = step[var]
    row += r
    col += c
    var = matrix[row][col]

print('Home!')

output

0 0 0 0 1 0 0 0
0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 0
0 0 0 1 0 0 1 0
0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0
1 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0

E W W W 1 S W W
N 1 1 N 1 S 1 N
N 1 E N 1 S 1 N
N W W 1 S W 1 N
N 1 N 1 S 1 1 N
N W 1 1 S 1 E N
1 N W W W 1 1 N
E N 1 1 1 1 E N

There is a path.
(7, 7) go N
(6, 7) go N
(5, 7) go N
(4, 7) go N
(3, 7) go N
(2, 7) go N
(1, 7) go N
(0, 7) go W
(0, 6) go W
(0, 5) go S
(1, 5) go S
(2, 5) go S
(3, 5) go W
(3, 4) go S
(4, 4) go S
(5, 4) go S
(6, 4) go W
(6, 3) go W
(6, 2) go W
(6, 1) go N
(5, 1) go W
(5, 0) go N
(4, 0) go N
(3, 0) go N
(2, 0) go N
(1, 0) go N
(0, 0) go E
Home!

Arne · Answer 3 · 2017-11-08T16:53:47.683

As a variant to @程名锐's post, this implementation of a DFS will also return the first path it has found. And as a general advice, if you don't care about the path being optimal, a DFS will usually serve you better than a BFS.

Note that we also have to make sure not to run in circles, since this graph is not a tree.

# for convenience
matrix = [
    ["0", "0", "0", "0", "1", "0", "0", "0"],
    ["0", "1", "1", "0", "1", "0", "1", "0"],
    ["0", "1", "0", "0", "1", "0", "1", "0"],
    ["0", "0", "0", "1", "0", "0", "1", "0"],
    ["0", "1", "0", "1", "0", "1", "1", "0"],
    ["0", "0", "1", "1", "0", "1", "0", "0"],
    ["1", "0", "0", "0", "0", "1", "1", "0"],
    ["0", "0", "1", "1", "1", "1", "0", "0"]
]
num_rows = len(matrix)
num_cols = len(matrix[0])

# just to be a bit more flexible, could also be passed as a function argument
goal_state = (num_rows - 1, num_cols - 1)


def dfs(current_path):
    # anchor
    row, col = current_path[-1]
    if (row, col) == goal_state:
        return True

    # try all directions one after the other
    for direction in [(row, col + 1), (row, col - 1), (row + 1, col), (row - 1, col)]:
        new_row, new_col = direction
        if (0 <= new_row < num_rows and 0 <= new_col < num_cols and  # stay in matrix borders
                matrix[new_row][new_col] == "0" and                  # don't run in walls
                (new_row, new_col) not in current_path):             # don't run in circles
            # try new direction
            current_path.append((new_row, new_col))
            if dfs(current_path):  # recursive call
                return True
            else:
                current_path.pop()  # backtrack


# result a list of coordinates which should be taken in order to reach the goal
result = [(0, 0)]
if dfs(result):
    print("Success!")
    print(result)
else:
    print("Failure!")

Prints:

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (6, 1), (6, 2), (6, 3), (6, 4), (5, 4), (4, 4), (3, 4), (3, 5), (2, 5), (1, 5), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7)]

The first (but for sure not shortest) correct path a DFS with the pathing preferences right -> left -> down -> up encounters.

Python breadth-first search matrix print path

3 Answers3

Linked