使用 scipy 搜索图的示例

Question

我很难找到有关如何在scipy 中使用和获取各种搜索算法的路径的教程/示例。

google 中最常见的就是这个例子，在这个例子的末尾有一些错误，带括号。

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
path = []
i = i2

while i != i1:
   path.append(word_list[i])
   i = predecessors[i]

path.append(word_list[i1])
print path[::-1]i2]

我没有输入，所以我无法复制它，但我认为只需删除 i2] 即可。

我的主要问题是如何搜索计算所有索引的图形，而不是给出它indices=i1，这是一个可选参数。同样，如何使用 Floyd-Warshall 方法并获取从任何i,j索引到任何其他i,j索引的路径。我的部分困惑是缺乏对前辈矩阵真正是什么以及如何解析它的描述。

有没有更详尽的教程，或者有人可以举一些简单的例子来梳理和理解吗？

Answer 1

我将使用这个无向图作为例子：

首先我们需要表示节点 i 到 j 距离的矩阵：

import numpy as np
from scipy.sparse.csgraph import shortest_path

M = np.array([[ 0,  7,  9,  0, 0, 14],
              [ 7,  0, 10, 15, 0,  0],
              [ 9, 10,  0, 11, 0,  2],
              [ 0, 15, 11,  0, 6,  0],
              [ 0,  0,  0,  6, 0,  9],
              [14,  0,  2,  0, 9,  0]])

现在我们叫

D, Pr = shortest_path(M, directed=False, method='FW', return_predecessors=True)

这里D是最短距离矩阵，Pr是前辈矩阵。D[i, j]给出从节点 i 到节点 j 的最短距离，并Pr[i, j]给出从点 i 到点 j 的最短路径中前一个节点的索引。如果从节点 i 到节点 j 没有任何路径，则 Pr[i,j] = -9999。随着method='FW'我们选择了弗洛伊德- Warshall算法。

最后我们可以使用前辈矩阵定义一个函数来获取从节点 i 到节点 j 的最短路径的节点列表：

def get_path(Pr, i, j):
    path = [j]
    k = j
    while Pr[i, k] != -9999:
        path.append(Pr[i, k])
        k = Pr[i, k]
    return path[::-1]

要获得从节点 0 到节点 4 的最短路径：

In [16]: get_path(Pr,0,4)
Out[16]: [0, 2, 5, 4]

In [17]: D[0,4]
Out[17]: 20.0

编辑：可能值得一看networkx包：

import numpy as np
from scipy.sparse.csgraph import shortest_path

M = np.array([[ 0,  7,  9,  0, 0, 14],
              [ 7,  0, 10, 15, 0,  0],
              [ 9, 10,  0, 11, 0,  2],
              [ 0, 15, 11,  0, 6,  0],
              [ 0,  0,  0,  6, 0,  9],
              [14,  0,  2,  0, 9,  0]])

D, Pr = shortest_path(M, directed=False, method='FW', return_predecessors=True)