finding path in directed graph

Printable View

• 12-16-2009
lordofdarkness
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
• 12-16-2009
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?
• 12-16-2009
slingerland3g
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.
• 12-16-2009
lordofdarkness
Quote:

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.
• 12-16-2009
quzah
Sounds like all you really want is the permutations between A and D.

Quzah.
• 12-16-2009
0rion
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.
• 12-17-2009
lordofdarkness
Thank you all for your great help. Orion's algorithm solved my problem.
• 12-17-2009
quzah
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.