有向图中从一个顶点到另一个顶点的最短路径
我的图是有向的并且非常大。图中的顶点代表城镇，边代表从一个城镇到另一个城镇的巴士行驶路线。目标是找到从一个顶点到另一个顶点的路径。该算法考虑公交车之间的换乘时间非常重要。
我会使用 Dijkstra 算法，但它从整个图表出发并找到一种方法。我需要找到一些从顶点到顶点的“最佳”方法。我所说的“最好”是指传输时间最短，但这不是最重要的一点。
My graph is directed and very large. The vertices in the graph represent towns, and the edges represents bus travel routes from town to town. The goal is to find a path from one vertex to another. It is very important that the algorithm takes into account the transfer time between buses.
I would use Dijkstra's algorithm, but it goes from the whole graph and finds one way. I need to find a few of "the best" ways from vertex to vertex. By "the best" I mean with the shortest transfer times, but this is not the most important point.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果需要查找多个最短路径，请参阅这个问题。
If you needs to find more than one shortest paths, refers to this question.
换乘巴士的“换乘时间”是一个重要的变量，最容易在图中表示为额外的顶点。假设边上的权重代表公交车之间的行程时间，您还可以使用节点和边来代表两辆公交车之间的换乘时间。
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.
我不确定转移术语，但是许多人（例如戈德伯格，桑德斯等）完成了与时间相关的高速公路层次结构工作，您可以在谷歌（dblp，或任何科学电子图书馆）上搜索。对于大陆大小的静态数据集，它们的速度要快数千倍，并且适用于动态和静态场景。
im not sure with transfer term, but there are time dependent highway hierarchy work done by many like goldberg , sanders etc, you can search that on google(dblp, or on any scientific e-lib). For continent size static datasets they are thousands of time faster and are for both dynamic and static scenarios.