graph-theory - 有向图中从一个顶点到另一个顶点的最短路径

Question

我的图表是有向的并且非常大。图中的顶点代表城镇，边代表从城镇到城镇的公共汽车旅行路线。目标是找到从一个顶点到另一个顶点的路径。该算法考虑到公交车之间的换乘时间是非常重要的。

我会使用 Dijkstra 的算法，但它来自整个图表并找到一种方法。我需要找到一些从顶点到顶点的“最佳”方式。“最好的”是指最短的转会时间，但这不是最重要的一点。

Answer 1

If you needs to find more than one shortest paths, refers to this question.

Answer 2

The "transfer time" for changing buses is an important variable and would be easiest to express as extra vertices in the graph. Assuming the weights on the edges represent travel times between buses, you can also use nodes and edges to represent transfer time between two buses.

Answer 3

我不确定转移术语，但许多人（如戈德堡、桑德斯等）完成了与时间相关的高速公路层次结构工作，您可以在 google（dblp 或任何科学 e-lib）上进行搜索。对于大陆大小的静态数据集，它们的速度要快数千倍，并且适用于动态和静态场景。