Question

Python中networkx中shortest_path使用的是哪一种最短路径方法

是Dijkstra算法吗？

Answer 1

不全是。依据传入的参数决定调用哪种算法。

看源码：至少涉及了dijkstra、广度优先/深度优先算法。

if source is None:
        if target is None:
            ## Find paths between all pairs.
            if weight is None:
                paths=nx.all_pairs_shortest_path(G)
            else:
                paths=nx.all_pairs_dijkstra_path(G,weight=weight)
        else:
            ## Find paths from all nodes co-accessible to the target.
            directed = G.is_directed()
            if directed:
               G.reverse(copy=False)

            if weight is None:
                paths=nx.single_source_shortest_path(G,target)
            else:
                paths=nx.single_source_dijkstra_path(G,target,weight=weight)

            # Now flip the paths so they go from a source to the target.
            for target in paths:
                paths[target] = list(reversed(paths[target]))

            if directed:
                G.reverse(copy=False)
    else:
        if target is None:
            ## Find paths to all nodes accessible from the source.
            if weight is None:
                paths=nx.single_source_shortest_path(G,source)
            else:
                paths=nx.single_source_dijkstra_path(G,source,weight=weight)
        else:
            ## Find 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)

追问

这个没包含source确定，arget不确定的情况哦？

追答

可能是我贴的有问题，其实源码中是配对的（从1开始数，第4个else和第1个if配对）。建议自行查看源码，可以用wingIDE4.1，非常方便。另这里贴出的是networkx.shortest_paths.shortest_path方法的源码，另有networkx.shortest_path方法（使用标准的BFS）