满足特定边约束的最短路径

Question

假设您有一个具有加权边的图，并希望找到最短路径，但有一个额外的警告，根据先前边的其他属性，必须满足其他约束。我能想到的最好的例子是航班或公共汽车类型。其中节点是城市，边是航班/路线，例如，边权重是价格。现在你想找到最便宜的票，但是你不能在你当前的巴士或飞机到达之前乘坐公交车或飞机离开。因此，在本例中，您可能有一个类似于元组列表(city1、city2、价格、持续时间、出发时间)的列表，目标是找到最便宜的“可行”路径，以便获得departure_time>culmative_time的优势。我想不出任何真正好的或有效的解决方案。

Answer 1

使用Dijkstra算法。但是，每次沿一条边移动到新顶点时，都会更新该顶点的累积时间。

当前不再提供(总时间超过其提供的时间)的该顶点之外的任何边都将被删除。

如果发现该边是下一个最便宜的边，则从该顶点引出当前未提供但将在适当时间提供的任何边，加上等待所需的时间以及到下一个顶点的行进时间。