Observation: For each node, we can reuse it's min path to destination, so we don't have to recalculate it(dp). Also, the moment we discover a cycle, we check if it's negative. If it's not, it will not affect our final answer, and we can say that it is not connected to the destination(wether it does or not).
Pseudo code:
Given source node u and dest node v
Initialize Integer dp array that stores min distance to dest node, relative to source node. dp[v]= 0, everything else infinite
Initialize boolean onPath array that stores wether the current node is on the path we are considering.
Initialize boolean visited array that tracks wether the current path has been done(initially all false)
Initialize int tentative array that stores the tentative value of a node. (tentative[u] = 0)
return function(u).
int function(int node){
onPath[node] = true;
for each connection u of node{
if(onPath[u]){ //we've found a cycle
if(cost to u + tentative[node] > tentative[u]) //report negative cycle
continue; //safely ignore
}
if(visited[u]){
dp[node] = min(dp[node], dp[u]); //dp already calculated
}else{
tentative[u] = tentative[node] + cost to u
dp[node] = min(function(u), dp[node])
}
visited[node] = true;
onPath[node] = false;
return dp[node];
}
I'm aware this algorithm won't cover the case where destination is part of a negative cycle, but besides that, is there anything wrong with algorithm? If not, what is it called?
You can't "safely ignore" a positive sum cycle because it might be hiding a shorter path. For example, suppose we have a graph with arcs u->x (10), u->y (1), x->y (10), y->x (1), x->v (1), y->v (10). The shortest u-v path is u->y->x->v, of length 3.
In a bad execution, the first three calls look like
function(u)
function(x)
function(y)
The out-neighbors of y are v, yielding a y->v path of length 10; and x, but the cycle logic suppresses consideration of this arc, so y is marked as visited with distance 10 (not 2). As a result we miss the shortest path.