Tutorial :Find all possible path between two nodes in a undirected graph



Question:

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


Solution:1

A Depth-First Search does this job.


Solution:2

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


Solution:3

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);  }  


Solution:4

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 []  


Solution:5

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.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »