分类：无权最短路径

2021
06-23

python3实现无权最短路径的方法

问题描述现有一个有向无权图。如下图所示： 问题：使用某个顶点s作为输入参数，找出从s到所有其他顶点的最短路径。说明：因为是无权图，因此我们可以为每台边赋值为1。这里选择v3为s作为起点。问题分析此时立刻可以说，从s到v3的最短路径是长为0的路径，标记此信息，得到下图。 现在开始寻找从s出发距离为1的顶点。这些顶点肯定是与s邻接的顶点，很明显，v1，v6从s出发只需要一条边就到了。所以，从s出发距离为1的顶... 继续阅读 >