Recursive DFS shortest path implementation not working as expected

Question

For a university assignment we have to implement a recursive naive shortest path algorithm for a weighted graph. It should check all the routes, and from that we can find the shortest.

We have been working on a Python script for a lot of time now, but we cannot get it to work properly. This is what we have now:

import numpy as np
global paths
paths = []

class Path:
        def __init__(self):
            self.NodeArray = [];
            self.Weight = 0;


def vindpaden(start,end,pad):
    pad.NodeArray.append(start)
    print "path so far: " + str(pad.NodeArray)
    global paths
    print "Start:" + str(start) + ", " + "end: " + str(end)
    if start == end:
        print "returning"
        paths.append(pad)
    else:
        for j in range(len(graph)):
            if (j not in pad.NodeArray) and graph[start][j] != -1:
                newpaths = vindpaden(j,end,pad)

graph = np.loadtxt("input2.txt")
graph = graph.astype(int)

start = 0
end = 1

path = Path()
vindpaden(start,end,path)

print "###### results:"
for p in paths:
    print "length: " + str(p.Weight) + ", path: " + str(p.NodeArray)

We are using an adjacency matrix as input. For testing, we are using the simple testing graph:

With the following adjacency matrix (where -1 means no connection):

-1 -1  1 -1
 3 -3 -1 -1
 2  2 -1  1
-1  2 -1 -1

This results in the following output:

path so far: [0]
Start:0, end: 1
path so far: [0, 2]
Start:2, end: 1
path so far: [0, 2, 1]
Start:1, end: 1
returning
path so far: [0, 2, 1, 3]
Start:3, end: 1
######
length: 0, path: [0, 2, 1, 3]

So you can see it finds a path from point 0 to point 1 via 2, after that it should add the path [0,2,1] to the array paths and continue looking for paths from point 2. Instead, it return the (incorrect) path [0,2,1,3]. In the end, the only path in the array paths is [0,2,1,3], which is also strange.

This is what we expect the output to be:

path so far: [0]
Start:0, end: 1
path so far: [0, 2]
Start:2, end: 1
path so far: [0, 2, 1]
Start:1, end: 1
returning
path so far: [0, 2, 3]
Start:3, end: 1
path so far: [0 ,2, 3, 1]
Start:1, end: 1
returning
######
length: 0, path: [0, 2, 1]
length: 0, path: [0, 2, 3, 1]

Please note that we are not using the property weight at this moment. Any help would be greatly appreciated!

Jim

Zachary Cross · Accepted Answer · 2015-09-17 17:46:08Z

1

It looks like your issue is that you are only ever create a single instance of Path(), which results in that instance's NodeArray getting corrupted. What I think is happens is as follows:

You get to the point where the NodeArray contains [0, 2, 1].
The function detects that it has reached the target, and thus goes back to the most recent node to check the rest of the potential paths.
Going from node 2, the next node after 1 is 3, so 3 is added to the NodeArray list. Because the list hasn't been cleared, the new node (3) is just added to the end, resulting in [0, 2, 1, 3].
Now, because 1 is already in your current NodeArray, the if statement if (j not in pad.NodeArray) and graph[start][j] != -1: fails and the function stops.

I think what you need to do is to create a new Path() every time you call vindpaden(), and copy the current Path's NodeArray into the new Path.

answered Sep 17, 2015 at 17:46

Zachary Cross

2,3281 gold badge17 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jim Daniël Teunis Over a year ago

I found the problem, and it is indeed exactly like you say. :) I solved it by passing deepcopy(pad), instead of pad. I was expecting Python to pass-by-value, but after reading up on it it seems Python uses it's own tricks for passing variables.

Collectives™ on Stack Overflow

Recursive DFS shortest path implementation not working as expected

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related