It's rather simple due to the directed acyclic nature of the problem we are guaranteed no cycles in the graph. Hence a simple DP algorithm suffices. We first define the DP state to be:
F(x) = the minimum distance from the last node
Then our recurrence becomes:
D(x) = min { weight(x,y) + D(y) } where y > x and y <= N-1.
Base case is simply D(last node) = 0 as we are already on the required node.
We augment it with a simple backtracking array to keep track of the best path. Note if you want to keep track of all paths you need to modify the condition to handle equality cases as opposed to just min cases.
Sample code below:
Code:
#define MAX_NODES 1001
#define INF (1 << 30)
int dp[MAX_NODES]; // dp table
int bt[MAX_NODES]; // backtracking table
int adjmat[MAX_NODES][MAX_NODES]; // adjacency matrix
void backtrack(int n, int sz) {
if (n >= sz-1) { printf(" %d\n", n); return; }
printf(" %d ->",n);
backtrack(bt[n],sz);
}
int main() {
int N;
scanf("%d",&N);
// read the matrix
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int v;
scanf("%d",&v);
adjmat[i][j] = v;
}
}
// use the dp algorithm
dp[N-1] = 0;
for (int i = N-2; i >= 0; i--) {
dp[i] = INF;
for (int j = i+1; j < N; j++) {
if (dp[j] + adjmat[i][j] < dp[i]) {
dp[i] = dp[j] + adjmat[i][j];
bt[i] = j;
}
}
}
printf("The minimum cost is %d\n",dp[0]);
// backtrack the path
backtrack(0, N);
return 0;
}
That being said, Dijkstra is faster but this is a simple DP approach to the problem.
finding path in directed graph
Originally Posted by EVOEx
