python - 计算 Dijkstra 算法中的跳跃次数？

Question

numpy 中计算 dijkstra 算法使用的跳转次数的最快方法是什么？我有一个 10000x10000 元素连接矩阵，并使用 scipy.sparse.csgraph.dijkstra 来计算填充距离矩阵和前驱矩阵。我的天真的解决方案如下:

import numpy as np
from numpy.random import rand
from scipy.sparse.csgraph import dijkstra

def dijkway(dijkpredmat, i, j):
    """calculate the path between two nodes in a dijkstra matrix"""
    wayarr = []
    while (i != j) & (j >= 0):
        wayarr.append(j)
        j = dijkpredmat[i,j]
    return np.array(wayarr)

def jumpvec(pmat,node):
    """calculate number of jumps from one node to all others"""
    jumps = np.zeros(len(pmat))
    jumps[node] = -999
    while 1:
        try:
            rvec = np.nonzero(jumps==0)[0]
            r = rvec.min()
            dway = dijkway(pmat, node, r)
            jumps[dway] = np.arange(len(dway),0,-1)
        except ValueError:
            break
    return jumps

#Create a matrix
mat = (rand(500,500)*20)
mat[(rand(50000)*500).astype(int), (rand(50000)*500).astype(int)] = np.nan
dmat,pmat = dijkstra(mat,return_predecessors=True)

timeit jumpvec(pmat,300)
In [25]: 10 loops, best of 3: 51.5 ms per loop

~50msek/节点是可以的，但是将距离矩阵扩展到 10000 个节点会将时间增加到~2sek/节点。 Jumpvec 也必须执行 10000 次...

Answer 1

这是一个(渐近最优)O(n) 算法。

创建一组未访问的顶点，最初是除源顶点之外的所有顶点。将源的跳转向量条目初始化为 0 到其自身。当集合不为空时，弹出一个元素 v。使用前趋矩阵，收集 v 和列表中的每个连续祖先，直到到达已访问过的元素。以相反的顺序迭代列表，将每个节点 w 的跳转向量条目设置为其父节点的条目加 1，然后从集合中删除 w。