LEMON C++中带约束的最短路径求解：如何避免连续红色弧？

核心思路 #

要避免路径中出现两条连续红色弧，核心是扩展状态空间：把每个节点的状态拆分为两种情况：

• 状态1：到达该节点时，最后一条弧不是红色（或当前是起点，无前置弧）
• 状态2：到达该节点时，最后一条弧是红色

通过这种拆分，我们可以在遍历过程中严格控制转移规则：

• 若当前状态是「最后弧为红色」，则下一条弧不能是红色
• 若当前状态是「最后弧非红色」，则下一条弧可任意选择

具体实现步骤 #

1. 定义扩展状态与距离存储 #

我们用std::pair封装节点和状态标记，同时维护每个状态的最短距离：

#include <map>
#include <queue>
#include <vector>
#include <algorithm>

// 定义状态：节点 + 是否最后一条弧为红色
using State = std::pair<ListDigraph::Node, bool>;

// 存储每个状态的最短距离，初始化为无穷大
std::map<State, int> dist;

// 初始化起点状态：起点无前置弧，两种状态的初始距离都为0
ListDigraph::Node s = ...; // 替换为你的起点节点
const int INF = 1e9;
// 先初始化所有可能状态为无穷大（可选，也可在后续判断时动态处理）
for (ListDigraph::NodeIt n(g); n != INVALID; ++n) {
    dist[{n, false}] = INF;
    dist[{n, true}] = INF;
}
dist[{s, false}] = 0;
dist[{s, true}] = 0;

2. 带状态约束的Dijkstra实现 #

由于LEMON默认Dijkstra不支持状态扩展，我们手动实现带状态的优先队列遍历：

// 优先队列：按距离升序排列，存储(当前距离, 状态)
using PQElement = std::pair<int, State>;
std::priority_queue<PQElement, std::vector<PQElement>, std::greater<PQElement>> pq;

// 起点两种状态入队
pq.push({0, {s, false}});
pq.push({0, {s, true}});

// 记录前驱弧与状态，用于后续回溯路径（可选）
std::map<State, std::pair<ListDigraph::Arc, State>> prev;

while (!pq.empty()) {
    auto [current_dist, current_state] = pq.top();
    pq.pop();

    auto [u, last_is_red] = current_state;

    // 当前状态已找到更短路径，跳过
    if (dist[current_state] < current_dist) continue;

    // 遍历节点u的所有出弧
    for (ListDigraph::OutArcIt a(g, u); a != INVALID; ++a) {
        ListDigraph::Node v = g.target(a);
        int arc_len = length[a];
        bool arc_is_red = (color[a] == "red");
        int new_dist = current_dist + arc_len;

        // 判断是否允许转移：连续红色弧直接跳过
        if (last_is_red && arc_is_red) continue;

        State new_state = {v, arc_is_red};
        // 更新更优路径
        if (new_dist < dist[new_state]) {
            dist[new_state] = new_dist;
            prev[new_state] = {a, current_state};
            pq.push({new_dist, new_state});
        }
    }
}

3. 获取目标节点的最短路径 #

对于目标节点t，取两种状态下的最小距离作为最终最短路径长度：

ListDigraph::Node t = ...; // 替换为你的目标节点
int shortest_dist = std::min(dist[{t, false}], dist[{t, true}]);

如果需要回溯路径，可通过prev映射反向推导：

// 选择距离更优的终点状态
State end_state = (dist[{t, false}] <= dist[{t, true}]) ? State{t, false} : State{t, true};
std::vector<ListDigraph::Arc> path;

// 反向回溯至起点
while (end_state != State{s, false} && end_state != State{s, true}) {
    auto [a, prev_state] = prev[end_state];
    path.push_back(a);
    end_state = prev_state;
}

// 反转得到从起点到终点的顺序
std::reverse(path.begin(), path.end());

扩展说明 #

这种状态扩展方法可以灵活适配更复杂的约束：比如最多允许k条连续红色弧，只需将状态改为(节点, 当前连续红色弧数量)，调整转移规则即可。

内容的提问来源于stack exchange，提问作者Claudio Tomasi