Thread: All Paths Between Two Nodes in Matrix

  1. #1
    Registered User
    Join Date
    Jun 2014
    Posts
    3

    All Paths Between Two Nodes in Matrix

    hi,I have a adjacency matrix.(router adjacency matrix in network).The result should be the router ID.I mean, print all the possible paths from source router to target router(ROUTER id>> 1 - 2 - 3 - 4 so there are four one router).I get the error in the output.)
    Code:
    #include<stdio.h>
    #include<conio.h>
    /* graph:  Pointer to the starting of mXn matrix
       i, j: Current position of the robot (For the first call use 0,0)
       m, n: Dimentions of given the matrix
       pi:   Next index to be filed in path array
       *route[0..pi-1]: The path traversed by robot till now (Array to hold the
                      path need to have space for at least m+n elements) */
    
    void displayAllroutesUtil(int *graph, int i, int j, int m, int n, int *route, int pi)
    {
        int k,l;
    
    // Reached the bottom of the matrix so we are left with
        // only option to move right
        if (i == m - 1)
        {
            for (k = j; k < n; k++)
                route[pi + k - j] = *((graph + i*n) + k);
            for (l = 0; l < pi + n - j; l++)
               printf("%d ",route[l]);
            printf("\n ");
            return;
        }
    // Reached the right corner of the matrix we are left with
        // only the downward movement.
    
        if (j == n - 1)
        {
            for (k = i; k < m; k++)
                route[pi + k - i] = *((graph + k*n) + j);
            for (l = 0; l < pi + m - i; l++)
                printf("%d ",route[l]);
            printf("\n ");
            return;
        }
    
      // Add the current cell to the path being generated
        route[pi] = *((graph + i*n) + j);
    
    // Print all the paths that are possible after moving down
        displayAllroutesUtil(graph, i+1, j, m, n, route, pi + 1);
    
    
        displayAllroutesUtil(graph, i, j+1, m, n, route, pi + 1);
    // Print all the paths that are possible after moving diagonal
        // printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1);
    
    }
    
    // The main function that prints all paths from top left to bottom right
    void displayAllroutes(int *graph, int m, int n)
    {
        int route[m+n];
        displayAllroutesUtil(graph, 0, 0, m, n, route, 0);
    }
    
    
    int main()
    {
        int graph[4][4] = { {0, 1, 1,0}, {1, 0, 0,1},{1, 0, 0,1},{1, 1, 1,0} };
    
    
    
    
        displayAllroutes(*graph, 2, 4);
        return 0;
    }
    Last edited by unhappyhuman; 06-09-2014 at 05:35 PM.

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,824
    1. I suggest using meaningful variable names.
    2. Post the real output and what you think the output should be.
    Edit: 3. Use at least meaningful parameter names

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Jun 2014
    Posts
    3
    code update

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    I second stahta, post your relevant output.

    Also, describe what your algorithm is. If I had to take a stab at navigating an adjacency matrix, my naive approach would be to check the first row for the target value and follow the set values from there. So if the first row is ( 1, 1, 0 0 ) and we want the node denoted by index 3, I would then check rows 0 and 1 because the 0 and 1 elements of the array are set. But because we just checked row 0, we know it's a dud so recursively checking it infinite times is pointless so I'd also include a history as well of which rows have been traversed. But that's just me. What's your approach?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-19-2014, 07:32 PM
  2. All paths between two nodes
    By paths000 in forum C++ Programming
    Replies: 2
    Last Post: 11-23-2012, 02:33 AM
  3. All paths between two nodes
    By DeanWinchester in forum C Programming
    Replies: 1
    Last Post: 12-29-2011, 01:17 PM
  4. Ignore paths???
    By gransken in forum C++ Programming
    Replies: 12
    Last Post: 11-29-2008, 05:30 AM
  5. Compiler Paths...
    By Cobra in forum C++ Programming
    Replies: 5
    Last Post: 09-26-2006, 04:04 AM

Tags for this Thread