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 - 最短路径长度 和 Networkx的加权图的所有最短路径？，但这些都没有完全回答我的问题。我也仔细查看了networkx的文档和谷歌上的其他文章，但还是没有找到答案。有人能帮我提供这个信息吗？谢谢！

Answer 1

这段话的意思是，它也会在“典型”的情况下运行Dijkstra算法。你可以查看源代码，里面显示这其实只是一些条件判断。

http://networkx.lanl.gov/_modules/networkx/algorithms/shortest_paths/generic.html#shortest_path

 ...
 if source is None:
        if target is None:
            if weight is None:
                paths=nx.all_pairs_shortest_path(G)
            else:
                paths=nx.all_pairs_dijkstra_path(G,weight=weight)
        else:
            raise nx.NetworkXError(\
                "Target given but no source specified.")
    else: # source specified
        if target is None:
            if weight is None:
                paths=nx.single_source_shortest_path(G,source)
            else:
                paths=nx.single_source_dijkstra_path(G,source,weight=weight)
        else:
            # shortest source-target path
            if weight is None:
                paths=nx.bidirectional_shortest_path(G,source,target)
            else:
                paths=nx.dijkstra_path(G,source,target,weight)

    return paths

Answer 2

这是一种叫做广度优先搜索（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