求助python的最短路径问题

Python016

求助python的最短路径问题,第1张

这是一个深度优先搜索算法（Deepth First Search, DFS）

算法核心是不断递归，直到找到目标，入队一种可能方案，return返回上一递归，再次尝试以当前点开始计算有没有其他方案，如有则继续递归并入队，如没有则再次return

简单来说就是这样的结构：

def dfs(position, value):

# position 传参位置，value 传参到现在的计算结果

if 到达目标:

判断value是否比最短路径短

      return value

else:

for x in position的所有可能下一路径:

if x在路径列表中:

# 不能有重复路径，变成回环

continue

else:

获取路径x的值

改变position

  入队 dfs(new_position, value+x

这个代码用的是字典存储每个点可到达的点以及路程

然后深度优先搜索

不懂再追问

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

看源码：至少涉及了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)