如何在带权有向图中找到满足最低成本要求（≥X）的最短通路？

核心问题拆解 #

我们要找的是从起点s到终点t、总权重≥X、边数最少的通路，允许重复经过顶点和边，图中可能包含环。

具体实现方案 #

1. 先做基础路径计算 #

先用Dijkstra算法（边权非负时）或Bellman-Ford算法（存在负权但无负环时）预处理两个关键数据：

• d_s[v]：起点s到每个顶点v的最短路径权重
• d_t[v]：每个顶点v到终点t的最短路径权重（可以通过反向建图后跑同算法得到）

通过这组数据先快速判断基础情况：

• 如果d_s[t] ≥ X，那s到t的最短路径就是答案；
• 如果d_s[t] < X，则需要结合环来累加权重，或者寻找更长的简单通路。

2. 处理含正权环的场景 #

若图中存在总权重w(C) > 0的环C，且存在通路s→u→C→u→t（u是环上节点），则可以通过重复走环来凑够权重：

• 计算基础通路s→u→t的总权重base = d_s[u] + d_t[u]
• 计算需要走环的次数k = ceil((X - base) / w(C))
• 最终通路为s→u + 重复k次环C + u→t，总权重为base + k*w(C)，边数为对应路径的边数之和
• 遍历所有可到达的正权环，取边数最少的组合即可

3. 无正权环的场景 #

此时所有环的权重≤0，重复走环只会增加边数却无法提升总权重，因此只需在**s到t的所有简单通路（不重复顶点）**中筛选：

• 用DFS结合剪枝：
  • 记录当前路径的权重和边数；
  • 若当前权重≥X，立即记录边数并剪枝（继续走只会增加边数）；
  • 若当前路径边数已超过已找到的最优解，直接剪枝；
  • 对每个顶点，记录到达它时「边数最少对应的最大权重」，如果当前路径到达该顶点时边数更多、权重更小，直接剪枝。

4. 修复反向遍历算法的问题 #

反向遍历思路可行，但需要补充关键终止条件：

• 从t出发反向遍历，记录到每个顶点v的最大权重路径（因为反向时要尽可能凑够X的权重）；
• 当反向到s时，若路径权重≥X，记录边数；
• 若遍历中发现某个顶点的所有反向路径权重都无法达到X，且无正权环可利用，直接终止遍历，判定无可行通路。

示例验证（你的案例） #

以你提到的图为例，起点0、终点2、X=12：

• 基础最短路径0→1→2权重为10（不足12），0→4→3→2权重为13（≥12）；
• 图中无正权环，因此直接取边数最少的权重达标通路，即0→4→3→2，符合预期。

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