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

Question

我的图形很直接，而且非常大。图中的顶点表示城镇，边缘表示从城镇到城镇的公交路线。目标是找到从一个顶点到另一个顶点的路径。该算法考虑到总线之间的传输时间非常重要。

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

Answer 1

改变巴士的“转换时间”是一个重要的变量，并且最容易表达为图中的额外顶点。假设边上的权重表示总线之间的传输时间，还可以使用节点和边来表示两条总线之间的传输时间。

Answer 2

即时通讯术语不确定，但有许多时间依赖的高速公路层次结构工作，如goldberg，sanders等，您可以在google（dblp或任何科学电子图书馆）上进行搜索。对于大陆尺寸的静态数据集，它们要快上千倍，适用于动态和静态场景。

Answer 3

如果您需要查找多条最短路径，请参阅this question。