递归 DFS 最短路径实现未按预期工作

Question

对于大学作业，我们必须为加权图实现递归朴素最短路径算法。它应该检查所有路线，从中我们可以找到最短的路线。

我们已经在 Python 脚本上工作了很长时间，但我们无法让它正常工作。这就是我们现在拥有的：

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)

我们使用邻接矩阵作为输入。对于测试，我们使用简单的测试图：

具有以下邻接矩阵（其中-1表示无连接）：

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

这导致以下输出：

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]

所以你可以看到它找到了一条从点0经点2到点1的路径，之后它应该将路径[0,2,1]添加到数组路径中并继续寻找从点2开始的路径。而不是，它 return （不正确的）路径 [0,2,1,3]。结果数组paths中的路径只有[0,2,1,3]，这也很奇怪。

这是我们期望的输出：

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]

请注意，我们目前没有使用属性权重。任何帮助将不胜感激！

吉姆

Answer 1

您的问题似乎是您只创建了一个 Path() 实例，这导致该实例的 NodeArray 被损坏。我认为发生的情况如下：

您到达 NodeArray 包含 [0, 2, 1] 的地步。
函数检测到它已经到达目标，因此返回到最近的节点以检查剩余的潜在路径。
从节点 2 开始，1 之后的下一个节点是 3，因此 3 被添加到 NodeArray 列表中。因为列表还没有被清空，所以新的节点（3）只是添加到最后，导致[0, 2, 1, 3].
现在，因为 1 已经在您当前的 NodeArray 中，if 语句 if (j not in pad.NodeArray) and graph[start][j] != -1: 失败并且函数停止。

我认为你需要做的是每次调用vindpaden()时创建一个新的Path()，并将当前Path的NodeArray复制到新 Path.

递归 DFS 最短路径实现未按预期工作

Recursive DFS shortest path implementation not working as expected

python

recursion

graph

depth-first-search