单源单目的地最短路径(DFS+DP)：时间复杂度与正确性问询

背景 #

针对带非负权重（可含环）的带权有向图，目标是实现固定源节点到固定目标节点的最短路径求解，设计了DFS+DP算法，核心思路如下：

• 用DFS遍历节点，计算每个节点到目标节点（DST）的最小代价
• 遍历邻节点，找出使(邻节点到目标的代价 + 边权)最小的路径
• 用DP数组缓存计算结果，避免重复计算
• 限制DFS递归深度为总节点数V，因为源到目标的最短路径最长包含V个节点（V-1条边），防止无限循环
• 递归基准条件：
  • 到达目标节点，返回0
  • 递归深度耗尽（剩余步数为0），返回INT_MAX
  • 节点状态已缓存，直接返回DP值

初始伪代码 #

int dfs(int u, int stops = V + 1, int &dst, vector<vector<pair<int, int>>> &adj, vector<int> &dp)
{
    if(u == dst) // 到达目标节点
        return 0; 
    if(stops == 0) // 无法继续递归
        return INT_MAX; 
    if(dp[u]!= -1)
        return dp[u];

    int res = INT_MAX;
    for(auto &[v, edgecost]: adj[u])
    {
        int vdstcost = dfs(v, stops - 1, dst, adj, dp); // 计算v到dst的最小代价
        if(vdstcost != INT_MAX)
            res = min(res, vdstcost + edgecost);
    }
    return dp[u] = res;
}

核心问题 #

1. 该代码的时间复杂度以边数E和节点数V表示是什么？
2. 该算法逻辑是否正确？能否在约束条件下处理所有场景并给出正确结果？

注：引入递归深度限制V后，时间复杂度难以直接判定，推测介于O(V+E)到O(VE)之间；若存在环（如A→...→B→...→A），递归会循环直到深度耗尽，因此不能简单定为O(V+E)。

修正后伪代码 #

由于初始DP未考虑剩余步数维度，更新为二维DP版本：

int dfs(int u, int stops, int dst, vector<vector<pair<int, int>>> &adj, vector<vector<int>> &dp)
{
    if(u == dst) // 到达目标节点
        return 0; 
    if(stops == 0) // 无法继续递归
        return INT_MAX; 
    if(dp[u][stops]!= -1)
        return dp[u][stops];

    int res = INT_MAX;
    for(auto &[v, edgecost]: adj[u])
    {
        int vdstcost = dfs(v, stops - 1, dst, adj, dp); // 计算v到dst的最小代价
        if(vdstcost != INT_MAX)
            res = min(res, vdstcost + edgecost);
    }
    return dp[u][stops] = res;
}

问题解答 #

1. 时间复杂度分析 #

• 初始一维DP版本：由于状态定义缺失剩余步数维度，缓存的结果无法区分不同剩余步数下的最优解，会导致大量无效递归重复计算，最坏时间复杂度为O(V*E)，且结果不可靠。
• 修正后二维DP版本：
  每个状态由(当前节点u, 剩余步数stops)唯一确定，总状态数为O(V^2)（u有V种可能，stops最多有V+1种可能）。
  每个状态会遍历当前节点的所有邻边，总边数为E，因此所有状态的总处理时间为O(V*E)。

2. 算法逻辑正确性 #

• 初始一维DP版本：不正确
  一维DP仅缓存了节点u到dst的最小代价，但未考虑剩余步数限制。同一节点在不同剩余步数下的最优解可能不同，一维DP会覆盖之前的缓存值，导致后续递归获取错误结果，甚至错过更优路径，无法正确处理带环的场景。
• 修正后二维DP版本：正确（非负权图约束下）
  • 基准条件合理：到达目标返回0，步数耗尽返回无穷大，已计算状态直接复用缓存，避免重复计算。
  • 状态转移正确：遍历所有邻边，累加边权与邻节点在剩余步数-1下的最小代价，取最小值作为当前状态的最优解，符合最短路径的递推逻辑。
  • 步数限制合理：非负权有向图中，最短路径最多包含V个节点（V-1条边），超过V步的路径必然包含非负权环，只会增加总代价，因此限制步数为V即可覆盖所有可能的最优路径，同时避免无限递归。

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