python - networkx shortest_path(G[, source, target, weight]) 函数的源算法

Question

我正在使用 networkx 做一些工作，并使用了两种最短路径算法:

 shortest_path(G[, source, target, weight]) 
 dijkstra_path(G, source, target[, weight])

据我所知，dijkstra_path(G, source, target[, weight]) 函数基于 dijkstra 的最短路径算法。我想知道 shortest_path(G[, source, target, weight]) 函数所基于的源算法。我需要它，因为我必须报告我使用过的算法。我搜索了一些 stackoverflow 页面，例如 Networkx - Shortest path length和 All shortest paths for weighted graphs with networkx?但他们并没有完全回答我的问题，我也仔细查看了 networkx 文档和谷歌上的其他文章，但没有找到答案。有人可以帮我提供这些信息吗？谢谢

Answer 1

这是一种广度优先搜索算法 (BFS)。这是单一来源问题的完整 NetworkX 代码。它还用于所有对的最短路径计算。对于源-目标最短路径，使用 BFS 的双向版本。这没有很好的记录，但文档和代码位于 http://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html。

def single_source_shortest_path(G,source,cutoff=None):
    level=0                  # the current level
    nextlevel={source:1}       # list of nodes to check at next level
    paths={source:[source]}  # paths dictionary  (paths to key from source)
    if cutoff==0:
        return paths
    while nextlevel:
        thislevel=nextlevel
        nextlevel={}
        for v in thislevel:
            for w in G[v]:
                if w not in paths:
                    paths[w]=paths[v]+[w]
                    nextlevel[w]=1
        level=level+1
        if (cutoff is not None and cutoff <= level):  break
    return paths