[algorithm] Find the paths between two given nodes?

If you want all the paths, use recursion.

Using an adjacency list, preferably, create a function f() that attempts to fill in a current list of visited vertices. Like so:

void allPaths(vector<int> previous, int current, int destination)
{
    previous.push_back(current);

    if (current == destination)
        //output all elements of previous, and return

    for (int i = 0; i < neighbors[current].size(); i++)
        allPaths(previous, neighbors[current][i], destination);
}

int main()
{
    //...input
    allPaths(vector<int>(), start, end);
}

Due to the fact that the vector is passed by value (and thus any changes made further down in the recursive procedure aren't permanent), all possible combinations are enumerated.

You can gain a bit of efficiency by passing the previous vector by reference (and thus not needing to copy the vector over and over again) but you'll have to make sure that things get popped_back() manually.

One more thing: if the graph has cycles, this won't work. (I assume in this case you'll want to find all simple paths, then) Before adding something into the previous vector, first check if it's already in there.

If you want all shortest paths, use Konrad's suggestion with this algorithm.

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to path

Get Path from another app (WhatsApp) How to serve up images in Angular2? How to create multiple output paths in Webpack config Setting the correct PATH for Eclipse How to change the Jupyter start-up folder Setting up enviromental variables in Windows 10 to use java and javac How do I edit $PATH (.bash_profile) on OSX? Can't find SDK folder inside Android studio path, and SDK manager not opening Get the directory from a file path in java (android) Graphviz's executables are not found (Python 3.4)

Examples related to graph-theory

Why is the time complexity of both DFS and BFS O( V + E ) Find all paths between two graph nodes When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? Difference between hamiltonian path and euler path How to draw a graph in LaTeX? When should I use Kruskal as opposed to Prim (and vice versa)? Find the paths between two given nodes? Finding all cycles in a directed graph Cycles in an Undirected Graph Best algorithm for detecting cycles in a directed graph

Examples related to pseudocode

Java balanced expressions check {[()]} From milliseconds to hour, minutes, seconds and milliseconds Find the paths between two given nodes? Quicksort: Choosing the pivot Algorithm to calculate the number of divisors of a given number