0

Can anybody give me a C Code to find all possible paths between two nodes? eg. if the graph has following edges 1-2 1-3 2-3 2-4 3-4

all paths between 1 and 4 are:

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Adrian
  • 5,603
  • 8
  • 53
  • 85
manoj
  • 1
  • 1
  • 1
  • Duplicate : http://stackoverflow.com/questions/713508/find-the-paths-between-two-given-nodes – Donnie May 21 '10 at 02:26

5 Answers5

3

A Depth-First Search does this job.

caf
  • 233,326
  • 40
  • 323
  • 462
Yin Zhu
  • 16,980
  • 13
  • 75
  • 117
  • Not really. DFS might give you a few paths, but not all of them. – Keith Randall May 21 '10 at 02:14
  • @Keith. Think about a dfs solution to n-queen problem. – Yin Zhu May 21 '10 at 02:37
  • The solution I think you're thinking of (loop over all possible squares, place a queen there if possible, and recurse) is not DFS. – Keith Randall May 21 '10 at 02:55
  • DFS doesn't revisit nodes it has visited already. If you're doing that (as you would need to do for the OP's problem), I wouldn't call it DFS. Wikipedia (http://en.wikipedia.org/wiki/Depth-first_search) agrees with me. I'll grant you, though, if you allow revisiting completed but not in progress nodes, you'll likely solve the OP's problem. – Keith Randall May 21 '10 at 04:11
  • 1
    @Keith: since the opening of the Wikipedia article says *Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking*, I'm not convinced that supports your thesis. It explicitly mentions back-tracking, which is what is needed to ensure complete coverage. – Jonathan Leffler May 21 '10 at 04:50
0

It is too late and not the C code but may be help others. This algo show how I implement it in java.

findPath(start) 
    Childs = getDirectChildsOf(start)
    foreach child in Childs
        tempRoute;
        tempRoute.add(start)
        if (child == end)
            return tempRoute.add(child) 
        else 
            tempRoute.add(findPath(child))
            if (tempRoute.last() == end)
                return tempRoute;

Here tempRoute may be a Route class that maintain a list of node. Able to add single node and other route to tempRoute. It also not find all possible path. for that you have to maintain a visited flag for each node.

Natwar Singh
  • 2,197
  • 4
  • 26
  • 42
0

(I'm assuming you don't want repeated nodes in your path - otherwise the number of possible paths is infinite.)

You can do a relaxation:

while (there is a change) {
  for (v in nodes(G)) {
    for (e in edges(v)) {
      paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v)
    }
  }
}

The result can still be exponential in the size of the input graph. Getting all paths is probably not what you want to do.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
0

This is a simple algorithm to the problem. It is not an optimal algorithm.

static struct {
  int value1;
  int value2;
  int used;
} data[] = {
  { 1, 2 },
  { 1, 3 },
  { 2, 3 },
  { 2, 4 },
  { 3, 4 },
};

enum { DATA_SIZE = sizeof data / sizeof *data };

static int output[DATA_SIZE];

int traverse(int from, int to, int depth) {
  output[depth++] = from;

  int i;
  if (from == to) {
    for (i = 0; i < depth; i++) {
      if (i) {
        printf("-");
      }
      printf("%d", output[i]);
    }
    printf("\n");
  } else {
    for (i = 0; i < DATA_SIZE; i++) {
      if (!data[i].used) {
        data[i].used = 1;

        if (from == data[i].value1) {
          traverse(data[i].value2, to, depth);
        } else if (from == data[i].value2) {
          traverse(data[i].value1, to, depth);
        }

        data[i].used = 0;
      }
    }
  }
}

int main() {
  traverse(1, 4, 0);
}
Brett Kail
  • 33,593
  • 2
  • 85
  • 90
  • hi bkail, thanks for your program.but i am finding some difficulties while checking for the following nodes,too many cycles are coming. can you try the following edges and find path having no repeated nodes between 1 and 4 {0, 5}, {1 ,4}, {0, 2}, {5 ,4 }, {1 ,2 }, {4 ,3 }, {3 ,10}, {1, 6 }, {6 ,2 }, {2 ,3 }, {2, 7 }, {3 ,14 }, {6, 7 }, {7, 8 }, {8, 10 }, {8, 9 }, {8 ,12 }, {8 ,14}, {5 ,11 }, {10 ,11 }, {10 ,13}, {10 ,9 }, {11 ,14 }, {11 ,12 }, {12 ,13 }, {13 ,14 }, – manoj Jun 02 '10 at 09:02
0

a recursive method:

findPaths(path = startNode, goal)
    paths = []
    if the last node in path is goal:
        return path
    for each node n connected to the last node in path:
        if n is not already on the path:
            paths.append(findPaths(path.append(node), goal))
    return paths //may still be []
themissinglint
  • 73
  • 5