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. #1
    Registered User
    Join Date
    Apr 2009
    Location
    Istanbul
    Posts
    11

    Exclamation 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. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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. #3
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    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. #4
    Registered User
    Join Date
    Apr 2009
    Location
    Istanbul
    Posts
    11
    Quote Originally Posted by EVOEx View Post
    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. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Sounds like all you really want is the permutations between A and D.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    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.
    The cost of software maintenance increases with the square of the programmer's creativity.

  7. #7
    Registered User
    Join Date
    Apr 2009
    Location
    Istanbul
    Posts
    11
    Thank you all for your great help. Orion's algorithm solved my problem.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 08:55 PM
  2. How to use C++ graphs?
    By eur0dad in forum C++ Programming
    Replies: 4
    Last Post: 10-14-2006, 12:37 PM
  3. Path Finding Using Adjacency List.
    By DeepBlackMagic in forum C++ Programming
    Replies: 7
    Last Post: 05-16-2005, 03:34 PM
  4. graph optimum path
    By Mist in forum C Programming
    Replies: 1
    Last Post: 03-06-2005, 04:39 PM
  5. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 12:21 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21