赞
踩
在研究路径选择和流量分配等交通问题时,常常会用到最短路算法。用最短路算法解决交通问题存在两个难点:
一、算法的选择和程序的编写。最短路算法有很多种改进算法和启发式算法,这些算法的效率不同,适用的网络也不相同。
二、构建一个算例网络很简单,但由于实际路网具有高度复杂性,因此将真实的拓扑路网导入最短路算法变得困难。
本期介绍dijkstra算法,并分享一些思路和实战案例。
最短路算法(shortest path algorithm)用于解决最短路径问题。常见的最短路算法有迪杰斯特拉算法(Dijkstra算法),Bellman-Ford算法,SPFA算法(队列优化的Bellma-Ford算法)和Floyd-Warshall算法等。
Dijkstra算法是典型的最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
算法步骤:
创建两个表,OPEN和 CLOSE。OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。
(1)访问路网中里起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。
(2)从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。
(3)遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。
(4)重复(2)、(3)步,直到OPEN表为空,或找到目标点。
单纯看理论部分比较难理解,下面分享一个Dijkstra算法的实例。
实例分析:
构建一个名为dijkstra()的函数,其功能是用dijkstra算法计算最短路。函数的参数分别设置为路网连通图(graph)、起点(start)和终点(end)。
# 函数:Dijkstra算法
先在简单的算例网络上测试一下我们的代码!
我们构造一个包含6个节点和9条边的算例网络。输入起点和终点(用空格隔开),用dijkstra算法计算最短路,并输出最短路径和最短距离的代码如下:
- # 定义路网连通图
- _ = float('inf') # 定义不可达距离
- graph=[[_, 2, _, 4, 7, _],
- [_, _, 2, _, 5, _],
- [_, _, _, _, _, 3],
- [_, _, _, _, 4, _],
- [_, _, 3, _, _, 1],
- [_, _, _, _, _, _],
- ]
- # 输入起点和终点
- r, s = input("输入起点和终点:").split()
- dis, road = dijkstra(graph, int(r), int(s))
- # 输出最短路结果
- print("最短路径:", road)
- print("最短距离:", dis)
程序的运行结果如下:
- >>>
- 输入起点和终点:0 5
- 最短路径: [0, 1, 2, 5]
- 最短距离: 7
- >>>
- 输入起点和终点:1 5
- 最短路径: [1, 2, 5]
- 最短距离: 5
- >>>
- 输入起点和终点:3 5
- 最短路径: [3, 4, 5]
- 最短距离: 5
虽然Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。下图是Dijkstra算法在4000节点网络上的演示,遍历过的节点由黑色圆圈表示。
由图中可以看出,Dijkstra算法从起始点开始向周围所有方向层层计算,经计算大量节点后,才到达目标点。所以该算法速度慢效率低。
下一篇文章为大家介绍floyd算法和真实地图导入!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。