Один источник — кратчайший путь с одним пунктом назначения (DFS + DP) — временная сложность?

Контекст:

Я хочу написать алгоритм поиска кратчайшего (наименьшей стоимости) пути от фиксированного источника к фиксированному узлу назначения во взвешенном ориентированном графе с неотрицательными весами (может иметь циклы).

Следующий алгоритм DFS + DP делает вышеописанное.

1. DO DFS — на каждом узле спросить, какова минимальная стоимость от текущего узла до узла DST.
2. Это делается путем опроса - из каждого соседа кто даст минимум (cost_to_dst + edgecost_to_neighbour)
3. После того, как мы найдем эту минимальную стоимость для DST, мы сохраним ее в массиве dp, чтобы нам не приходилось вычислять ее снова для этого узла.
4. Чтобы избежать бесконечного цикла рекурсивных вызовов dfs, мы ограничиваем глубину вызовов до V (количество всех узлов), поскольку максимальная длина кратчайшего пути от SRC до DST может быть V.
5. Итак, базовые условия для dfs/рекурсивных вызовов: i) если вы достигли летнего времени, верните 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)

Изменить - исправлен псевдокод

ДП также необходимо рассмотреть вопрос «нет». осталось остановок, как указано в ответе ниже. код ниже обновлен для использования 2D DP

int dfs(int u, int stops, int dst, vector<vector<pair<int, int>>> &adj, vector<vector<int>> &dp)
{
    if (u == dst) // reached dst
        return 0; 
    if (stops == 0) // can't go on anymore
        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); // min cost from v to dst
        if (vdstcost != INT_MAX)
            res = min(res, vdstcost + edgecost);
    }
    return dp[u][stops] = res;
}