I want to write an algorithm for finding the shortest(least cost) path from a fixed source to a fixed destination node in a weighted directed graph with non negative weights (can have cycles).
The following DFS + DP algorithm does the above.
(cost_to_dst + edgecost_to_neighbour)
dp
array, so that we don't have to compute it again for that node.V
(no. of total nodes) as the max length of the shortest path from SRC to DST can be V.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;
}
What will be the Time Complexity of this code in terms of E (no. of edges) and V (no. of nodes)?
Is this logically correct? i.e Will this algorithm give me the correct answer for every scenario within constraints?
The 4th point of introducing limit of depth V to recursive calls is making it difficult for me to analyse the time complexity. But I'm confident it will be somewhere between O(V+E)
to O(VE)
.
Imagine a path --> A --->...----> B ---->...----> A. In such a case, the recursive calls will go into loops until (V) depth is exhausted. So the TC can't simply be O(V+E)
The DP also needs to consider no. of stops left , as pointed in the below answer. below code is updated to use 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;
}
If I understand the question correctly, you intend to have a working algorithm that only relies on memoization and depth-first traversal, without the notion of visited/not-visited, nor priority queues. But it doesn't always work:
The algorithm you've specified will not always find the path because it may store INT_MAX
distances in dp[u]
when actually there is a path from u
to the target:
u
alone. The result depends on the number of stops that are still available. It might be that with just 2 stops available, there is no way to reach the target, but with 5 there is a way. So you need to memoize the results per node and per stops.Not a breaking issue, but:
stops
could be πβ1, as you already give it a node as argument, which counts as one, leaving you only πβ1 for further expansions (i.e. number edges to follow).Once the above is fixed, we can consider this "bad" case:
We have π nodes, where each has two outgoing edges, one to itself, and one to the "next" node, and where all weights are 1. Let π£1 be the source and π£π the target. Assume that the loop-edges are always visited first in the worst case. Then if we ignore memoization for a moment, a DFS starting at π£1 will try these paths, all of length πβ1 (i.e. with π nodes):
Only at the last attempt will the target be found and will all nodes receive a non-infinite assignment in the dp
array.
If we consider memoization to prune the tree, then at node π£1 we will have π different values of stops
that can occur at that node. For π£2 we will have one less possibility for stops
, ...etc, up to For π£π where stops
can be nothing else than 0. So to to write to all these dp
entries (i.e. the worst case), we will need π + πβ1 + πβ2 + ... + 1 visits. All other node visits, coming via the alternative edge to the same node will benefit from memoization. So those count for the same number of operations.
So we get a complexity for this scenario that is O(πΈΒ²).
If you would limit to graphs without self-loops, then you can set up a similar reasoning with a graph that has an even number of nodes π and where the nodes in an odd-even pair reference each other, like this:
Wikipedia lists some of the popular algorithms to find a shortest path in a graph. Even though Dijkstra's algorithm can solve the problem of finding shortest paths from a given vertex to all vertices in the graph, it can be used for a single destination as well, where it simply returns when that vertex has been found. It has a worst case time complexity of O(πΈ + πlogπ).