c++ - 使用图表的机场旅行

Question

有人可以帮我想出一种更好的方法来适应这些条件下的 Dijkstra 算法吗？到目前为止，我所想到的一切都不好。

输入示例:

GP4578 MADRID 01:00 PORTO 02:00

IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00

AB5874 VALENCIA 05:40 BERLIM 10:00

"VALENCIA 05:00 05:30"这是中途停留，都是30min左右。航类有到达和离开时间、航类号、始发地和目的地城市。

所以，我需要得到从一个城市到另一个城市的最短路径，好的，没问题。我找不到如何构建它，自上周以来我一直在尝试。有人可以给我想法吗？我的顶点是哪个，每个城市还是每个航类？如何使用边缘？如何中途停留？

Answer 1

基本上，您可以使用每个城市/机场作为节点并将航类作为它们之间的连接来对其进行建模。连接/航类的权重就是时间。如果您假设所有中途停留都是 30 分钟(在简化模型中)，那么您可以为每个访问节点添加额外成本(在本例中为 30 分钟)

查看此维基百科页面 (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) 上的图片。现在查看这张包含繁忙机场航类的 map http://www.worldmapsatlas.com/world-map/thematic/world-air-routes-map.html了解如何构建模型。