Finding all possible paths from given start node to finish node

Question

I am trying to print all paths from source to destination in a graph which uses adjacency list.It is weighted and directed. I'm trying to do it in BFS.Thanks for the help. I am getting only one path. How do I get to print other paths?

Here is BFS function:

void BFS(struct Graph *G,QUEUE *q)
{
    int j,i=0;
    while(!isEmpty(q))
    {
        int source = dequeue(q);
        printf("%d ",source);
        path[i]=source;
        i++;
        if(source==bitis)//source==end
        {
            for(j=0;j<i;j++)
                printf("%d ",path[j]);
        }
        struct node *head = G->adjList[source]->next;
        while(head)
        {
            if(G->adjList[head->source]->marked)
            {
                head = head->next;
                continue;
            }
            G->adjList[head->source]->marked = 1;
            enqueue(head->source,q);
            head = G->adjList[head->source]->next;
        }
    }
}

Here is structs:

struct node{
    int source;
    int w;
    int marked;
    struct node *next;
};
struct Graph{
    int V;
    int E;
    struct node **adjList;
};

Here is adjList:

[0]->[2]->[1]
[1]->[2]
[2]->[3]->[1]
[3]->[0]
[4]->[3]->[2]

Output:4 3 0

this graph:

5 node, 9 edge (A=0,B=1,C=2,D=3,E=4)
start node: 4 end node: 0

this graph:

5 node, 8 edge (A=0,B=1,C=2,D=3,E=4)
start node: 4 end node: 0

I want all paths between the two values entered by the user. If user enter 3 and 2

I want the output to be this way:

3 -> 0 -> 2
3 -> 0 -> 1 -> 2

I hope I could express my question. My english so bad. Thank you.

Hello, I guess it doesn't matter. Because according to the given start and end points, all path will be found. I edited my question. I put a picture. @JimMischel — dogac, Jan 08 '19 at 15:38
Yes, it does matter. The problem is easier to solve if you know that there are no cycles in the graph. But the graph examples show that we can't assume the graph is acyclic. — Jim Mischel, Jan 08 '19 at 15:59
In your example graphs, the nodes are labeled with letters, but you say "start node 4, end node 0," for the second graph. Which node (A, B, D, D, E) corresponds to node 4? I think you need to fix your question. — Jim Mischel, Jan 10 '19 at 04:28
See [1](https://stackoverflow.com/a/48718818/3992939) and [2](https://stackoverflow.com/a/48920440/3992939) — c0der, Jan 10 '19 at 05:37

score 0 · Answer 1 · answered Jan 06 '19 at 07:03

This idea may be helpful

create a queue which will store path(s) of type vector
initialise the queue with first path starting from src

Now run a loop till queue is not empty
   get the frontmost path from queue
   check if the lastnode of this path is destination
       if true then print the path
   run a loop for all the vertices connected to the
   current vertex i.e. lastnode extracted from path
      if the vertex is not visited in current path
         a) create a new path from earlier path and 
             append this vertex
         b) insert this new path to queue

Print all paths from a given source to a destination using BFS

score 0 · Answer 2 · answered Jan 09 '19 at 03:03

bitis is not clear. If it means end node of path, path may or may not exist in directed graph and it can fail. One approach is to traverse graph starting with one node at a time and every node visited will have queued nodes giving its path. If there are n nodes graph will be traversed n times and queue will become empty n times.

Finding all possible paths from given start node to finish node

2 Answers2