UPDATE: My algorithm is wrong. See this graph: https://pastebin.com/zfuVCRut In processing the elements this way some nodes are marked visited, while they actual reduce distance. Here, node 2 is marked with a large distance, but it actually leads to the shortest path.
Suppose I wish to know the minimum distance between two nodes a
and b
in a unweighted graph. I know we can BFS to do this, but I wanted to do it in reverse.
Assume that the graph is undirected, connected, and unweighted.
So, we want to compute f(a, b)
. To do this, we have to traverse some edge from a
that brings us closer to b
.
We traverse the neighbours of a
, and compute the minimum of f(a', b)
.
Now, computing this way will lead to cycles (f(a, b)
calls f(a', b)
which will again call f(a, b)
), but, if we call some function again, that is clearly sub-optimal for the parent function. Our goal is to minimize f(a, b)
, and if we return to f(a, b)
after some steps, that is clearly sub-optimal as it adds unnecessary edges.
To counter this we initialize the value to some very large value. Note that this may mean that f(a', b)
may be higher than expected, but we don't care, we wish to minimize f(a, b)
.
Pseudcode:
int dis[N][N] // N is the number of nodes, initially all -1
function f(a, b) {
if (a == b) {
return 0;
}
if (a and b are neighbours) {
return 1;
}
if (dis[a][b] != -1) {
return dis[a][b];
}
dis[a][b] = infinity;
min_dis = infinity;
for (a' in neighbours of a) {
min_dis = min(min_dis, f(a', b) + 1);
}
dis[a][b] = min_dis;
return ans;
}
Does this algorithm work?
Thanks!