狄克斯特拉算法
图12.44 三条可以选择的路径
图12.45 选择段数最少的路径 图12.46 选择用时最短的路径
图12.47 起点到终点的线路图
图12.48 起点->A->B 图12.49 起点->A->终点
- 到达顶点B用时更短的路径,时间从8分钟缩短到7分钟
- 到达终点用时更短的路径,时间从无穷大缩短到12分钟
图12.50 起点->A->B->终点
图12.51 起点到终点的线路图
图12.52 实现狄克斯特拉算法的流程
graph = {}
01 graph["start"] = {}
02 graph["start"]["A"] = 3
03 graph["start"]["B"] = 8
04 graph["A"] = {}
05 graph["A"]["B"] = 4
06 graph["A"]["end"] = 9
07 graph["B"] = {}
08 graph["B"]["end"] = 2
graph["end"] = {}
09 costs = {}
10 costs["A"] = 3
11 costs["B"] = 8
12 costs["end"] = float("inf")
operated = []
13 def get_lowest_cost_node(costs): #定义函数并传入参数costs
14 lowestCost = float("inf") #最低开销,初始值为无穷大
15 lowestCostNode = None #开销最低顶点,初始值为None
16 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) #获取下一个要操作的顶点
print("从起点到终点的最短用时是"+str(costs["end"])+"分钟")
原创文章,作者:guozi,如若转载,请注明出处:https://www.sudun.com/ask/89367.html