c++ - 修改 Bellman-Ford 以支持第二个边权重

Question

所以给定初始和最终节点，我需要使用 Bellman-Ford 算法来：

1. 找到一条成本最低的路径，同时

2. 停留在特定时间段内

每条边都有成本和时间/持续时间权重。

但是，我不知道如何优化它，也许是优先级队列？我会改变放松功能还是整个程序？

Answer 1

这可以通过对 Bellman-Ford 的轻微修改来完成。像往常一样，外部循环将运行最多 N-1 次，其中 N 是顶点数。

您必须存储每个顶点的距离和时间，而不是存储从源到顶点的距离。（由dist及time以下表示）

内部循环将稍作修改：-

1. 遍历所有顶点。
2. 对于每个顶点 v，迭代它的邻居。

3. 对于每个邻居 u：（Tmax 是允许的最长时间）

   if (dist[v] + cost_of_edge[v -> u] < dist[u]) then
       if (time[v] + time_of_edge[v -> u] < Tmax) then
           dist[u] = dist[v] + cost_of_edge[v -> u]
           time[u] = time[v] + time_of_edge[v -> u]
       end if
   end if
   else if (dist[v] + cost_of_edge[v -> u] == dist[u]) then
        if (time[v] + time_of_edge[v -> u] < time[u]) then
            time[u] = time[v] + time_of_edge[v -> u]
        end if
   end if
   

第一个 if 条件就像正常的 Bellman-Ford 一样：试图找到到 的最小距离u，同时确保到达所需的时间u不超过 Tmax。

第二个 if 条件是新的：假设有一条P从源到u成本的路径，dist[u]并且需要时间time[u]来遍历。现在假设我们找到了另一条P'具有相同成本dist[u]但花费更少时间的time[u]路径 - 然后我们想选择这条路径，因为这将允许我们从 到达更多顶点u。

假设我们不选择路径P'，而是选择P，在这种情况下，在算法的更深处，可能有一条从u另一个顶点到另一个顶点的路径，比如x，由于时间限制，我们无法考虑。P'但是，如果从 time to traverse P'< time to traverse开始选择路径，则可能考虑此路径P。