单源 - 单目的地最短路径（DFS + DP） - 时间复杂度？

Question

背景：

我想编写一个算法，用于在具有非负权重（可以有循环）的加权有向图中找到从固定源到固定目标节点的最短（最低成本）路径。

以下 DFS + DP 算法实现了上述功能。

DO DFS - 在每个节点询问从当前节点到 DST 节点的最小成本是多少。
这是通过询问每个邻居哪一个给出最小值来完成的
2. (cost_to_dst + edgecost_to_neighbour)
找到 DST 的最小成本后，我们将其存储在
3. dp

    数组中，这样我们就不必为该节点再次计算它。

为了避免陷入递归 dfs 调用的无限循环，我们将调用深度限制为
4. V

   （总节点数），因为从 SRC 到 DST 的最短路径的最大长度可以为 V。

因此 dfs/递归调用的基本条件是：
5. i) 如果达到 DST，则返回 0。 ii) 如果耗尽 V dfs 调用，则返回 INT_MAX。 iii) 如果节点已被处理，则返回 dp[node]

伪代码：

int dfs(int u, int stops = V + 1, int &dst, vector<vector<pair<int, int>>> &adj, vector<int> &dp)
    {
        if(u == dst) // reached dst
            return 0; 
        if(stops == 0) // can't go on anymore
            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); // min cost from v to 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。 在这种情况下，递归调用将进入循环，直到 (V) 深度耗尽。所以TC不能简单地是O(V+E)

Answer 1

首先，在 𝑉 节点之后停止是正确的，但这意味着在您的伪代码中

stops

 的默认（初始）值可能是 𝑉−1，因为您已经给它一个节点作为参数，这很重要作为一个，只留下 𝑉−1 进行进一步扩展（即要遵循的数字边）。

这是您可以考虑的最坏情况：

我们有 𝑛 节点，其中每个节点都有两个传出边，一个到自身，一个到“下一个”节点。令 𝑣

1 _{为源，𝑣}𝑛 _{为目标。假设在最坏的情况下总是首先访问循环边。然后，从 𝑣}1 _{开始的 DFS 将尝试这些路径，所有长度为 𝑉−1（即具有 𝑉 节点）：}

𝑣
• 1 _{→ ... → 𝑣}1 _{→ 𝑣}1 _{→ 𝑣}1
𝑣
• 1 _{→ ... → 𝑣}1 _{→ 𝑣}1 _{→ 𝑣}2
𝑣
• 1 _{→ ... → 𝑣}1 _{→ 𝑣}2 _{→ 𝑣}2
𝑣
• 1 _{→ ... → 𝑣}1 _{→ 𝑣}2 _{→ 𝑣}3
𝑣
• 1 _{→ ... → 𝑣}2 _{→ 𝑣}2 _{→ 𝑣}2
𝑣
• 1 _{→ ... → 𝑣}2 _{→ 𝑣}2 _{→ 𝑣}3
...
𝑣
• 1 _{→ 𝑣}2 _{→ ... → 𝑣}𝑛−1 _{→ 𝑣}𝑛

只有在最后一次尝试时才会找到目标，并且所有节点都会在

dp

 数组中收到非无限分配。换句话说，在这种情况下，记忆并没有真正带来任何收益，因为除了最后一个搜索之外的所有搜索都被 

stops==0

 中止。因此，为了计算最坏情况的复杂性，我们可以简单地忽略记忆方面。

为了确定时间复杂度，我们可以观察到，在除目标节点之外的每个节点上，我们都做出了两种选择：一次继续循环边缘，一次继续前向边缘。这意味着我们有 2 次幂的可能性，扩展和回溯的工作就像递增一个具有 𝑛−1 位的二进制数，从 0 开始到 2

𝑛−1^。

这意味着我们的最坏情况时间复杂度为 O(2

𝑛−1^{)，即 O(2}𝑉^)。

如果您限制为没有自循环的图，那么您可以使用具有 2𝑛 节点且奇偶对中的节点相互引用的图建立类似的推理，如下所示：