Python算法-最短路径问题

狄克斯特拉算法

假设从一个起点到终点之间有三条可以选择的路径，如图12.44所示。

图12.44 三条可以选择的路径

使用广度优先遍历法可以找出段数最少的一条路径，如图12.45中所示的红色线条表示的路径。但是，段数最少的路径并不一定是用时最短的路径，如图12.46中所示的红色线条表示的就是用时最短的路径（线条上的数字表示时间，单位是分钟）。如果要找出用时最短的路径就需要使用另一种算法——狄克斯特拉算法。

图12.45 选择段数最少的路径图12.46 选择用时最短的路径

下面通过一个例子来介绍一下如何使用狄克斯特拉算法。仍然是以起点和终点之间的多条路径为例，从起点到终点的线路图如图12.47所示。图中的每个数字表示的是时间，单位是分钟。

图12.47 起点到终点的线路图

要找出从起点到终点用时最短的那条路径，就需要使用狄克斯特拉算法。使用狄克斯特拉算法主要包含以下四个步骤：

（1）找到可以在最短时间内到达的顶点。

（2）更新该顶点的相邻顶点的开销。顶点的开销是指从起点出发到达该顶点需要的时间。简单的说，这一步的目的是检查从起点到该顶点的相邻顶点是否有用时更短的路径，如果有，就更新其开销。

（3）对其它顶点都重复执行步骤（1）和步骤（2）。

（4）计算获得最短时间。

下面针对图12.47对每个步骤进行详细讲解。

步骤一：找到可以在最短时间内到达的顶点。由图12.47可知，到达顶点A需要3分钟，到达顶点B需要8分钟，而到达终点需要的时间未知，可以先假设为无穷大。所以，到达顶点A的用时是最短的。

步骤二：计算经过顶点A到达其各个相邻顶点所需的时间，并更新其开销。顶点A的两个相邻顶点是顶点B和终点，从起点经过顶点A到达顶点B（起点->A->B）需要7分钟，示意图如图12.48所示。从起点经过顶点A到达终点（起点->A->终点）需要12分钟，示意图如图12.49所示。

图12.48 起点->A->B 图12.49 起点->A->终点

现在找到了一条到达顶点B用时更短的路径，从起点直接到达顶点B需要8分钟，而经过顶点A到达顶点B只需要7分钟。由于找到了到达顶点B和终点的用时更短的路径，因此需要更新其开销。结果如下：

到达顶点B用时更短的路径，时间从8分钟缩短到7分钟
到达终点用时更短的路径，时间从无穷大缩短到12分钟

步骤三：对其它顶点重复执行步骤一和步骤二。

重复步骤一：找到可以在最短时间内到达的顶点。除了顶点A之外，可以在最短时间内到达的顶点是顶点B。

重复步骤二：计算经过顶点B到达其各个相邻顶点所需的时间，并更新其开销。这时会找到从起点到达终点用时最短的路径，示意图如图12.50所示。

图12.50 起点->A->B->终点

这样，对每个顶点（终点除外）都应用了狄克斯特拉算法，因此可以得出以下结论：

从起点到达顶点A需要3分钟

从起点到达顶点B需要7分钟

从起点到达终点需要9分钟

步骤四：计算获得最短时间。下面以图12.51为例，来了解如何使用代码来实现狄克斯特拉算法，应用狄克斯特拉算法找到从起点到达终点的最短时间。

图12.51 起点到终点的线路图

先来了解一下该例中实现狄克斯特拉算法的流程，其流程图如图12.52所示。

图12.52 实现狄克斯特拉算法的流程

下面编写获取从起点到达终点的最短时间的代码。具体步骤如下：

（1）定义一个空字典graph，该字典用来存储所有顶点到相邻顶点的开销。代码如下：

graph = {}

（2）在graph字典中存储起点的相邻顶点和到达相邻顶点的开销，代码如下：

01  graph["start"] = {}02  graph["start"]["A"] = 303  graph["start"]["B"] = 8

（3）在graph字典中存储顶点A的相邻顶点和到达相邻顶点的开销，代码如下：

04  graph["A"] = {}05  graph["A"]["B"] = 406  graph["A"]["end"] = 9

（4）在graph字典中存储顶点B的相邻顶点和到达相邻顶点的开销，代码如下：

07  graph["B"] = {}08  graph["B"]["end"] = 2

（5）因为终点没有相邻顶点，所以将终点定义为一个空字典，代码如下：

graph["end"] = {}

（6）定义一个字典costs，在字典中存储顶点A、顶点B和终点三个顶点的开销。因为不知道从起点到达终点需要多少时间，所以将终点的开销设置为无穷大，代码如下：

09  costs = {}10  costs["A"] = 311  costs["B"] = 812  costs["end"] = float("inf")

（7）定义一个数组operated，该数组用来记录操作过的顶点，代码如下：

operated = []

（8）定义get_lowest_cost_node()函数，应用该函数找出开销最低的顶点。代码如下：

13  def get_lowest_cost_node(costs):                    #定义函数并传入参数costs14      lowestCost = float("inf")                       #最低开销，初始值为无穷大15      lowestCostNode = None                           #开销最低顶点，初始值为None16      for n in costs:                                 #遍历所有顶点17          cost = costs[n]                             #获取当前顶点的开销18          if cost < lowestCost and n not in operated: #如果当前顶点开销更低且未操作过19              lowestCost = cost                       #将当前顶点的开销作为最低开销20              lowestCostNode = n                      #将当前顶点作为开销最低顶点21      return lowestCostNode                           #返回开销最低的顶点

（9）编写实现狄克斯特拉算法的代码，调用get_lowest_cost_node()函数获取开销最低的顶点，在while循环中更新该顶点的相邻顶点的开销。代码如下：

22  n = get_lowest_cost_node(costs)                     #获取开销最低顶点23  while n is not None:                                #在所有顶点都被操作过后结束循环24      cost = costs[n]                                 #获取当前顶点的开销25      neighbors = graph[n]                            #获取当前顶点的所有相邻顶点26      for i in neighbors.keys():                      #遍历当前顶点的所有相邻顶点27          newCost = cost + neighbors[i]               #从起点到当前顶点的相邻顶点的开销28          if costs[i] > newCost:                      #如果经过当前顶点到达相邻顶点更近29              costs[i] = newCost                      #更新相邻顶点的开销30      operated.append(n)                              #将当前顶点标记为已操作过31      n = get_lowest_cost_node(costs)                 #获取下一个要操作的顶点

（10）最后输出从起点到终点的最短用时，代码如下：

print("从起点到终点的最短用时是"+str(costs["end"])+"分钟")

运行上述代码，结果如图12.53所示。

原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/89367.html

Python算法-最短路径问题

相关推荐

aws ip范围，aws iam policy

为什么我的电脑提示没有软盘？（解决方案）

服务器性能监控工具

两台服务器负载均衡怎么设置的

发表回复