c++ - 在 3 个字符串向量中查找连接

Question

我用 C++ 编写了一些代码，它找到了两个城市之间通过道路或航班连接的最短路径。城市可以与直航或间接航班相连。用户可以像这样输入航班：

AAA AAG 300
AAA AAB 1
AAA AAG 298
AAB AAC 1
AAB AAG 297
AAC AAD 1
AAC AAG 296
AAD AAE 1
AAD AAG 295
AAE AAF 1
AAE AAG 294
AAF AAG 1

第一个字符串是离开城市，第二个是目的地，数字是飞行时间。我将这些值存储在 3 个向量中：

   vector<string> leavingCities;
   vector<string> destCities;
   vector<int> flightTimes;

我很难在这些向量中找到间接航班 - 我的意思是有时从 AAA 到 AAG 的直接飞行时间比通过 AAB、AAC、AAD、AAE 和 AAF 的间接飞行要大得多，然后我必须选择较短的路线并存储城市我路过。有没有办法找到最短的时间和路线？航班清单可能会有所不同，不一定要像这样。也许有一些更好的容器来存储这样的数据？请帮我。

Answer 1

你真的应该把你的问题分解成理解你将如何解决它，然后进入代码。如果您不了解如何解决它，通常仅编写代码将无济于事。

首先，您的问题可以归类为在图算法中查找最短路径。维基百科有一整页，但Dijkstra 的算法可能是最适合你的。

了解了方法之后，就可以着手实施了。如果你可以使用它们，那里有很多不错的图形库，比如Boost.Graph，但我怀疑作为一项任务，你会被要求从头开始自己实现它。但是，我不建议将 Boost 资源作为一个没有经验的程序员来查看——它们非常可怕，尽管一旦你有了更多的经验，这是一种很好的学习方式。

祝你好运

Answer 2

使用Dijkstra 算法找到最短路径。