时间戳

首页 > 解决方案 > 从城市 1 到达城市 N 的最短时间

algorithm - 从城市 1 到达城市 N 的最短时间

问题描述

有很多图问题需要对 BFS 算法进行一些修改。我刚遇到这个问题。我想到了这个问题，只是对标准 BFS 算法的扩展。该问题指出：

我们有一个国家，有 N 个城市和 M 个双向道路。每个城市都有一个红绿灯，只显示两种颜色，即绿色和红色。所有的红绿灯在每 T 秒后将颜色从绿色切换到红色，反之亦然。只有当红绿灯亮时，我们才能穿越城市。最初，所有交通灯都是绿色的。在任何一个城市，如果交通灯是红色的，那么我们必须等待它的灯变绿。行驶任何道路所需的时间是 C。我们必须找到从 1 到达城市 N 的最短时间。

注意：图不包含自环或多条边。

例如：

N=5,M=5,T=3,C=5

边缘是：

1 2,

1 3,

2 4,

1 4,

2 5。

这里从 1 到 5 的最短时间是 11 通过路径 1 2 5。我们可以在 5 秒内到达城市 2。然后等待 1 秒钟让灯变绿，然后等待 5 秒钟转到 5。

任何人都可以分享他解决这个问题的方法吗？无论是 BFS 问题还是其他需要的图算法？更好地理解psedoucode是否会与算法一起存在？

标签： algorithmgraphbreadth-first-searchdijkstra

解决方案

由于所有城市的初始状态相同，开关灯的频率相同，所有道路的持续时间相同，因此红绿灯对所有路线的延迟相等。

由于所有道路的持续时间都相同，这意味着 BFS 将是解决问题的有效方法。对标准算法的唯一调整是调整每个节点的时间，以解决由于交通信号灯造成的任何延迟。

（如果道路的持续时间不同，或者灯光切换不规则，则需要更高级的算法，例如 Dijkstra。）

推荐阅读