路由算法的简单路径

计算科学 算法 数据分析 数据集
2021-11-28 08:13:40

我目前正在研究地铁路径,但站在一个问题面前,没有编程知识,时间限制极短。可能我问的问题是微不足道的,但如果你能指出我正确的方向或正确的论坛,我会很高兴!

为特定城市地铁系统生成了所有可能的地铁路线,包括起始站、换乘站和出口站,我现在必须找到每条路线的车上旅行时间。我为路线的每个链接都有 excel 样式的数据,但是必须为(开始、转移、退出)的每个向量订购和添加这些数据,以便为我提供总旅行时间。

以以下路线为例:A -> B -> C 我有关于每条线路的旅行时间的信息,例如 A4 -> A5, A5 -> A6, A6 -> A, A -> ... -> B和 B3 -> B4, B4 -> B5, B5 -> B6, B6 -> ... -> C,其中每个 k = {An, Bm, C} 是一个车站,A 是起点,B 是换乘点和 C 是路线的出口点。

我如何编写一个程序,通过 excel 观察并为每条路线添加所有相关的旅行时间?

考虑到大约 50000 条路线,手动完成这可能会非常耗时。对此的任何帮助将不胜感激!如果有任何不清楚的地方,我很乐意尝试澄清我的意思。

最好的

1个回答

这种旅行时间估计的一个实际复杂情况是从一条线路/火车转移到另一条线路/火车所花费的时间。

如果您的目标只是最短旅行时间,那么有简单的相对快速的算法可以找到一条或所有“最佳”路线。请参阅Dijkstra对于单个起点和目的地的最短路径算法,或对于所有成对的起点和目的地的Floyd-Warshall 算法。

从提到“没有编程知识”和“excel 观察”这听起来好像您更喜欢某种电子表格实现。我认为这不会令人满意,但也许您可以找到一些支持资源来帮助您。