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
Not really. DFS might give you a few paths, but not all of them.
Keith Randall
2010-05-21 02:14:17
@Keith. Think about a dfs solution to n-queen problem.
Yin Zhu
2010-05-21 02:37: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
2010-05-21 02:55:06
@ Yes, it is. dfs is a family of search algorithms..
Yin Zhu
2010-05-21 03:03:26
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
2010-05-21 04:11:45
@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
2010-05-21 04:50:53
A:
(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
2010-05-21 02:18:21
A:
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);
}
bkail
2010-05-21 02:42:19
A:
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
2010-05-21 03:13:33
A:
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
2010-06-02 09:02:20
If you want to respond to an answer, leave a comment on it. Adding another answer is very confusing.
crazyscot
2010-06-02 09:21:02