使用 scipy 的搜索图示例

Question

我很难找到 tutorials/examples 如何在 scipy 中使用和获取各种搜索算法的路径。

google 中出现的最常见的是 this one，其中示例在括号结尾处有一些错误。

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的最短路径中前一个节点的索引。 Pr[i,j] = -9999 如果没有任何从节点 i 到节点 j 的路径。 method='FW' 我们选择 Floyd-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 networkx as nx

G = nx.from_numpy_array(M) # M is the adjacency matrix from above

In [14]: nx.shortest_path(G, 0, 4, weight='weight')
Out[14]: [0, 2, 5, 4]

In [15]: nx.shortest_path_length(G, 0, 4, weight='weight')
Out[15]: 20

使用 scipy 的搜索图示例

Examples for search graph using scipy

python

graph-theory

scipy