当前位置:文档之家› 最佳旅游路线规划问题

最佳旅游路线规划问题

最佳旅游路线规划问题
问题描述:如今的道路密度越来越大,收费道路也越来越多,因此选择最佳
路径是很现实的问题。

城市的道路是双向的,每条道路有固定的旅行时间以及所需支付的费用。

路径是由连续的道路组成。

总时间是各条道路旅行时间的和,总
费用是各条道路所支付费用的总和。

同样的出发地和目的地,如果路径A 比路径B 所需时间少且费用低,那么我们就说路径A 比路径B 好。

对于某条路径,
如果没有其他路径比它好,那么该条路径被称为最优路径。

下图给出了城市间旅行时所需的旅行时间等信息,请计算从北京出发,到其
他所有城市的最优路径,及路径上所需的旅行时间总和。

要求:建立无向网时,从Dijstra.txt 文件中读取数据建立无向网。

输出结果:输出格式为“旅游的起始、终止点,以及时间总和”
如:从北京出发,终点为广州,最佳路线是直达的,则输出结果应该为:北京->广州,旅行时间和为15
若从北京出发,终点为太原,最佳路线需要经过天津到达,则输出结果应该为:北京->天津->太原,旅行时间和为6。

相关主题