尝试从 P 矩阵打印最短路径

Question

我正在尝试使用此算法从路径矩阵 P 中打印出最短路径。

我的实现：

testmatrix=np.matrix('0,7,7,0,7,7,0,0,7;0,0,7,0,7,9,0,1,0;9,0,0,0,7,0,2,9,6;9,8,8,0,8,8,8,0,8;9,3,0,0,0,3,3,9,6;9,9,9,0,9,0,9,9,0;9,5,5,0,0,5,0,9,6;9,7,7,0,7,7,0,0,7;0,7,7,0,7,0,1,1,0')

def path(q,r):
    if (testmatrix[q,r] !=0):
        path(q,testmatrix[q,r])
        print("v "+str(testmatrix[q,r]))
        path(testmatrix[q,r],r)

当我调用它打印 v7 到 v8 的最短路径时：

path(7,8)

我得到一个打印出来的错误：

v 7
v 7
v 7
.
.
.
v 7
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-41-72a35ae59934> in <module>()
----> 1 path(7,8)

<ipython-input-40-7b3409c28cd1> in path(q, r)
      3         path(q,testmatrix[q,r])
      4         print("v "+str(testmatrix[q,r]))
----> 5         path(testmatrix[q,r],r)
      6 

... last 1 frames repeated, from the frame below ...

<ipython-input-40-7b3409c28cd1> in path(q, r)
      3         path(q,testmatrix[q,r])
      4         print("v "+str(testmatrix[q,r]))
----> 5         path(testmatrix[q,r],r)
      6 

RuntimeError: maximum recursion depth exceeded while calling a Python object

我不知道我是否在 Python 中达到了某个递归限制，或者我的实现是否（很可能）有问题。但老实说，我无法弄清楚我做错了什么。如果有人可以为我提供一些指导来解决这个问题，我将非常感激。

Answer 1

您的 0 权重与 python 的 0 索引冲突，因为您的索引是从 1 到 9 而不是 0 到 8。您可以通过从矩阵中减去 1 并将 -1 视为权重来解决此问题0 并切换到 python 索引世界。

matrix([[-1,  6,  6, -1,  6,  6, -1, -1,  6],
        [-1, -1,  6, -1,  6,  8, -1,  0, -1],
        [ 8, -1, -1, -1,  6, -1,  1,  8,  5],
        [ 8,  7,  7, -1,  7,  7,  7, -1,  7],
        [ 8,  2, -1, -1, -1,  2,  2,  8,  5],
        [ 8,  8,  8, -1,  8, -1,  8,  8, -1],
        [ 8,  4,  4, -1, -1,  4, -1,  8,  5],
        [ 8,  6,  6, -1,  6,  6, -1, -1,  6],
        [-1,  6,  6, -1,  6, -1,  0,  0, -1]])

现在索引从 0 到 8。如果元素为 -1，则表示它是最短路径。

代码：

import numpy as np
testmatrix=np.matrix('0,7,7,0,7,7,0,0,7;0,0,7,0,7,9,0,1,0;9,0,0,0,7,0,2,9,6;9,8,8,0,8,8,8,0,8;9,3,0,0,0,3,3,9,6;9,9,9,0,9,0,9,9,0;9,5,5,0,0,5,0,9,6;9,7,7,0,7,7,0,0,7;0,7,7,0,7,0,1,1,0')
testmatrix = testmatrix -1
def path(q,r):
    if (testmatrix[q,r] !=-1):
        path(q,testmatrix[q,r])
        print("v "+str(testmatrix[q,r]))
        path(testmatrix[q,r],r)

path(6,7)

结果：

v 4
v 2
v 5
v 8
v 0

或者如果你真的坚持使用 1-9 索引，你可以将 path 放入 newpath 并在那里完成工作：

import numpy as np
testmatrix=np.matrix('0,7,7,0,7,7,0,0,7;0,0,7,0,7,9,0,1,0;9,0,0,0,7,0,2,9,6;9,8,8,0,8,8,8,0,8;9,3,0,0,0,3,3,9,6;9,9,9,0,9,0,9,9,0;9,5,5,0,0,5,0,9,6;9,7,7,0,7,7,0,0,7;0,7,7,0,7,0,1,1,0')
def new_path (q1,r1,testmatrix):
    def path(q,r):
        if (testmatrix[q,r] !=-1):
            path(q,testmatrix[q,r])
            print("v "+str(testmatrix[q,r]+1))
            path(testmatrix[q,r],r)
    testmatrix = testmatrix-1
    q = q1-1
    r = r1-1
    path(q,r)


new_path(7,8,testmatrix)

结果：

v 5
v 3
v 6
v 9
v 1

尝试从 P 矩阵打印最短路径

Trying to print shortest path from P matrix

python

numpy

shortest-path

floyd-warshall