Thread: All paths between two nodes

Hello everyone, I have a task in which I need to store in an array all possible paths between two nodes, in this case, from the inicial node to the last one.

I'm trying to start but I have no ideas on how to.
I'll be using a matrix, I got all my adjacent vertex's stored in an Adjacency List and I coded a function that passes my Adjacency List to a matrix so I'll be using it.

Any ideas on how I could start ?

Maybe Dijkstra ?
Making it so that when I pass through each vertex, I have a flag storing it as 1 or 0, being 1 when he's visited and 0 when he hasn't been visited yet.

Why do you think you need a matrix? How much space will your matrix take up if you have, say, 100 nodes? 1000? You can easily write search/traversal algorithms that operate directly on adjacency lists. Google should help you there.

Do you know what Dijkstra's algorithm is used for? Perhaps you should read up on it (Dijkstra's algorithm - Wikipedia, the free encyclopedia). Then you can answer your own "maybe Dijkstra?" question. Google graph search or graph traversal algorithms and read up on some of the basic ones like BFS and DFS. Wikipedia is actually a great source of information on CS stuff like algorithms and data structures. From the Dijkstra's algorithm page, you can browse many other graph search algorithms like BFS and DFS. You need your search to be exhaustive, to try every possible path. Think about how you might modify some of those algorithms to "keep going" even after they found one path to the goal. Ask yourself whether an algorithm for finding the optimal path is at all appropriate for your problem.

You will need a visited flag to avoid getting stuck in a cycle, but don't let that exclude you from finding two valid paths that have the same prefix, e.g. A->B->C->D->F and A->B->C->E->F. That is, once you find a path to the goal, you probably don't want to go all the way back to the start again, you just want to back up part way. You will only need to clear the visited flag as far back as you "back out" of one path and try the next.