Q:

Recursive DFS shortest path implementation not working as expected

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

A:

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.

