# finding path in directed graph

This is a discussion on finding path in directed graph within the C Programming forums, part of the General Programming Boards category; hi everyone. i need to find all possible paths for directed graph with dynamic programming. let me clarify. i have ...

1. ## finding path in directed graph

hi everyone.
i need to find all possible paths for directed graph with dynamic programming.
let me clarify. i have a path from 1 to n and this is a straight line. every line has a value. i need a way where the cost is smallest. i take inputs as 2 dimensional array (a[i][j]) and i <= j.

....A..B..C..D
A..0..2..5..9
B......0..6..7
C..........0..5
D..............0

this is an example of inputs. i want to go D from A. its same for different n numbers.

A---B---C---D

Can you help me to find the dynamic programming algorithm.

whenever you want you can send me a e-mail or write under this topic
my email address is: lordofdarkness1903@yahoo.com.tr

2. What exactly do you want the algorithm to output? All possible paths? Because assuming there are edges between all nodes, there are an infinite number of paths. In your example there aren't, the possible paths are only ( A, B, C, D ) and ( A, C, D ). Well, assuming I read your matrix right.

Or do you want to calculate the shortest path?

3. He wants all paths of lesser or equal weight. The Dijkstra algorithm comes to mind. A short google search on that gave me actual code on this.

4. Originally Posted by EVOEx
What exactly do you want the algorithm to output? All possible paths? Because assuming there are edges between all nodes, there are an infinite number of paths. In your example there aren't, the possible paths are only ( A, B, C, D ) and ( A, C, D ). Well, assuming I read your matrix right.

Or do you want to calculate the shortest path?
first of all sorry for my english. i think i couldn't explain my problem properly.
no come back is allowed. you can think that A is the start point and D is the finish so all possible paths for 4 inputs are:
A-B-C-D
A-B-D
A-C-D
A-D.
in the matrix costs are written. i want to calculate the smallest cost from A to D.

5. Sounds like all you really want is the permutations between A and D.

Quzah.

6. 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.

7. Thank you all for your great help. Orion's algorithm solved my problem.

8. Really!? There's a shocker! Someone posted you a full working example of your assignment and it 'solved your problem'? Who saw that coming?

Quzah.

Popular pages Recent additions