问题：
根据一条自驾旅游路线图，可以知道城市之间的高速公路的长度以及该公路要收取的过路费用。编写一个程序，查找出出发地和目的地之间的最短路径，如果有若干条路径都是最短的，那么需要输出过路费最小的一条路径：
输入：
4 5 0 3 （表示4条断点，5条边。起点是0，终点是3）。
0 1 1 20 （表示0点和 1点 是相连的，路径长度是1，路费20，下面行表示相同的含义）。
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
关系图如下：
Snip20171006_1.png
思路，使用Dijkstra 算法。
Dijkstra 算法是解决单源最短路径的一种算法，基本的思路是首先找出离源点最近的点（标记为已经访问过），然后计算出源点经过这个点到达其它点的距离。如果源点经过这个点后可以使原来的距离变得更短，则更新源点到该点的距离。得到一个经过松弛后的数组。然后在对这个松弛后的数组中未被访问过的点做同样的处理，找出离源点最近的点，在计算出经过这个点到达其它点距离。按此进行迭代。
处理的过程如下：
1: 列出0到 其它点的距离。
Snip20171006_2.png
2:1和0点距离最近。计算出0经过1 到2 和3 的最短距离：
0点经过1点不能到达2点，所以0到2的距离保持不变，还是2。0点经过1到达3点的距离为3比0点直接到达3的距离4要小，所以进行更换。
Snip20171006_6.png
3:计算出0 距离2和3点哪个更近，2点比较近，计算出0点经过
2点到达3点的距离为3 和上一步一样，这时在计算费用，费用比上一步的小。更新0到3的最小费用为40.
Snip20171006_5.png
结束。
所以输出是：3 40。 表示 0～3的最短距离是3，花费是40.
源代码路径：
https://github.com/jackymail/algorithm/blob/master/Dijkstra_traval_planning_planning.c
网友评论