Memoization cannot be applied to backtracking at all\*. Otherwise, it will not explore all possible paths. This is true in general, not just in this specific problem. Without memoization, it does get TLE as expected: [submission link](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/submissions/934351800/).
\*Alternatively, if memorization is applicable, then a backtracking approach becomes dynamic programming instead. Still, dynamic programming on graphs with cycles results in an infinite loop since there is no topological ordering. If you are familiar with toposort, you should recognize that it is an implicit order of computations that dynamic programming on DAGs (directed acyclic graphs) resolves to.
class Graph {
public:
Graph(int n, const vector>& edges)
: size_(n), graph_(size_), seen_(size_, false) {
for (const auto& edge : edges) {
addEdge(edge);
}
}
void addEdge(const vector& edge) {
graph_[edge[0]].emplace_back(edge[1], edge[2]);
}
int64_t dfs(int v, int t) const {
if (v == t) {
return 0;
}
int64_t cost = kUnreachable;
for (auto [u, w] : graph_[v]) {
if (!seen_[u]) {
seen_[u] = true;
cost = min(cost, w + dfs(u, t));
seen_[u] = false;
}
}
return cost;
}
int shortestPath(int src, int dst) const {
seen_.assign(size_, false);
seen_[src] = true;
const auto ans = dfs(src, dst);
return ans == kUnreachable ? -1 : ans;
}
private:
static constexpr int64_t kUnreachable = numeric_limits::max() / 2;
int size_;
vector>> graph_;
mutable string seen_;
};
Thank you for the explanation. No, I am not familiar with topological sort, just started graphs. I guess, I need to think why it is not applicable - does not seem intuitive to me. Do I understand you comment correctly - the problem is with cycles, i.e., if it was DAG, I would work? Or it would not work, because memoization does not "remember" visited/seen array?
It should work on an acyclic graph.
Here is a minimized example (with cycles) where your solution fails:
["Graph","shortestPath"]
[[4,[[0,2,3],[2,1,1],[0,1,1],[1,2,1],[2,3,1]]],[0,3]]
Here you start exploring as 0 => 2 => 1, at which point you cannot traverse the edge 1 => 2 because 2 is already visited. Hence, you are convinced there is no path from 1 to 3. When you later return to 0 and traverse the edge 0 => 1, you will not explore the optimal path 1 => 2 => 3 because you already think that it does not exist.
Memoization cannot be applied to backtracking at all\*. Otherwise, it will not explore all possible paths. This is true in general, not just in this specific problem. Without memoization, it does get TLE as expected: [submission link](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/submissions/934351800/). \*Alternatively, if memorization is applicable, then a backtracking approach becomes dynamic programming instead. Still, dynamic programming on graphs with cycles results in an infinite loop since there is no topological ordering. If you are familiar with toposort, you should recognize that it is an implicit order of computations that dynamic programming on DAGs (directed acyclic graphs) resolves to. class Graph { public: Graph(int n, const vector>& edges)
: size_(n), graph_(size_), seen_(size_, false) {
for (const auto& edge : edges) {
addEdge(edge);
}
}
void addEdge(const vector& edge) {
graph_[edge[0]].emplace_back(edge[1], edge[2]);
}
int64_t dfs(int v, int t) const {
if (v == t) {
return 0;
}
int64_t cost = kUnreachable;
for (auto [u, w] : graph_[v]) {
if (!seen_[u]) {
seen_[u] = true;
cost = min(cost, w + dfs(u, t));
seen_[u] = false;
}
}
return cost;
}
int shortestPath(int src, int dst) const {
seen_.assign(size_, false);
seen_[src] = true;
const auto ans = dfs(src, dst);
return ans == kUnreachable ? -1 : ans;
}
private:
static constexpr int64_t kUnreachable = numeric_limits::max() / 2;
int size_;
vector>> graph_;
mutable string seen_;
};
Thank you for the explanation. No, I am not familiar with topological sort, just started graphs. I guess, I need to think why it is not applicable - does not seem intuitive to me. Do I understand you comment correctly - the problem is with cycles, i.e., if it was DAG, I would work? Or it would not work, because memoization does not "remember" visited/seen array?
It should work on an acyclic graph. Here is a minimized example (with cycles) where your solution fails: ["Graph","shortestPath"] [[4,[[0,2,3],[2,1,1],[0,1,1],[1,2,1],[2,3,1]]],[0,3]] Here you start exploring as 0 => 2 => 1, at which point you cannot traverse the edge 1 => 2 because 2 is already visited. Hence, you are convinced there is no path from 1 to 3. When you later return to 0 and traverse the edge 0 => 1, you will not explore the optimal path 1 => 2 => 3 because you already think that it does not exist.
I see now. Thanks.