How to modify dijkstra algorithm to find all possible paths?

Question

I know that could be asked before already but I cannot find it. I need to modify below dijkstra algorithm which works good for finding shortest path between 2 nodes but I need to find all possible paths also. I know it should be relatively easy to do this but so far I don't have idea how to do this simplest way. I'm using directed weighted graph.

    class Dijkstra
    {
        private List<Node> _nodes;
        private List<Edge> _edges;
        private List<Node> _basis;
        private Dictionary<string, double> _dist;
        private Dictionary<string, Node> _previous;

        public Dijkstra(List<Edge> edges, List<Node> nodes)
        {

            Edges = edges;
            Nodes = nodes;
            Basis = new List<Node>();
            Dist = new Dictionary<string, double>();
            Previous = new Dictionary<string, Node>();

            // record node 
            foreach (Node n in Nodes)
            {
                Previous.Add(n.Name, null);
                Basis.Add(n);
                Dist.Add(n.Name, double.MaxValue);
            }
        }

        /// Calculates the shortest path from the start
        ///  to all other nodes
        public void calculateDistance(Node start)
        {
            Dist[start.Name] = 0;

            while (Basis.Count > 0)
            {
                Node u = getNodeWithSmallestDistance();
                if (u == null)
                {
                    Basis.Clear();
                }
                else
                {
                    foreach (Node v in getNeighbors(u))
                    {
                        double alt = Dist[u.Name] + getDistanceBetween(u, v);
                        if (alt < Dist[v.Name])
                        {
                            Dist[v.Name] = alt;
                            Previous[v.Name] = u;
                        }
                    }
                    Basis.Remove(u);
                }
            }
        }

        public List<Node> getPathTo(Node d)
        {
            List<Node> path = new List<Node>();

            path.Insert(0, d);

            while (Previous[d.Name] != null)
            {
                d = Previous[d.Name];
                path.Insert(0, d);
            }

            return path;
        }

    public Node getNodeWithSmallestDistance()
        {
            double distance = double.MaxValue;
            Node smallest = null;

            foreach (Node n in Basis)
            {
                if (Dist[n.Name] < distance)       
                {
                    distance = Dist[n.Name];
                    smallest = n;
                }
            }

            return smallest;
        }


        public List<Node> getNeighbors(Node n)
        {
            List<Node> neighbors = new List<Node>();

            foreach (Edge e in Edges)
            {
                if (e.Origin.Equals(n) && Basis.Contains(n))
                {
                    neighbors.Add(e.Destination);
                }
            }

            return neighbors;
        }

       public double getDistanceBetween(Node o, Node d)
        {
            foreach (Edge e in Edges)
            {
                if (e.Origin.Equals(o) && e.Destination.Equals(d))
                {
                    return e.Distance;
                }
            }

            return 0;
        }


        public List<Node> Nodes
        {
            get { return _nodes; }
            set { _nodes = value; }
        }

        public List<Edge> Edges
        {
            get { return _edges; }
            set { _edges = value; }
        }

        public List<Node> Basis
        {
            get { return _basis; }
            set { _basis = value; }
        }

        public Dictionary<string, double> Dist
        {
            get { return _dist; }
            set { _dist = value; }
        }

        public Dictionary<string, Node> Previous
        {
            get { return _previous; }
            set { _previous = value; }
        }
    }
}

static void Main(string[] args)
        {
//Nodes initialisation goes here

Dijkstra d = new Dijkstra(_edges, _nodes);
d.calculateDistance(_dictNodes["A"]);
 List<Node> path = d.getPathTo(_dictNodes["C"]);
}

Answer 1

Here is how you can do it with BFS: the following (python) functions (modified BFS with a recursive path-finding function between two nodes) can be used to find all possible paths between two nodes in an acyclic graph:

from collections import defaultdict

# modified BFS
def find_all_parents(G, s):
    Q = [s]
    parents = defaultdict(set)
    while len(Q) != 0:
        v = Q[0]
        Q.pop(0)
        for w in G.get(v, []):
            parents[w].add(v)
            Q.append(w) 
    return parents

# recursive path-finding function (assumes that there exists a path in G from a to b)   
def find_all_paths(parents, a, b): 
    return [a] if a == b else [y + b for x in list(parents[b]) for y in find_all_paths(parents, a, x)]

For example, with the following graph (DAG) G given by

G = {'A':['B','C'], 'B':['D'], 'C':['D', 'F'], 'D':['E', 'F'], 'E':['F']}

if we want to find all paths between the nodes 'A' and 'F' (using the above-defined functions as find_all_paths(find_all_parents(G, 'A'), 'A', 'F')), it will return the following paths:

Answer 2

OK, I have actually modified Dijkstra class to do BFS as well and it got me all possible routes. I added this method:

public void BreadthFirst(Edge graph, LinkedList<String> visited) 
{
    LinkedList<String> nodes = graph.adjacentNodes(visited.Last());

    // Examine adjacent nodes
    foreach (String node in nodes) 
    {
        if (visited.Contains(node))
        {
            continue;
        }

        if (node.Equals(endNode))
        {
            visited.AddLast(node);

            printPath(visited);

            visited.RemoveLast();

            break;
         }
     }

    // In breadth-first, recursion needs to come after visiting adjacent nodes
    foreach (String node in nodes)
    {      
        if(visited.Contains(node) || node.Equals(endNode))
        {
            continue;
        }

        visited.AddLast(node);

        // Recursion
        BreadthFirst(graph, visited);

        visited.RemoveLast();
    }
}

Usage would be like this:

Dijkstra d = new Dijkstra(_edges, _nodes);

LinkedList<String> visited = new LinkedList<string>();  //collecting all routes
visited.AddFirst(start);

d.BreadthFirst(graph, visited);

Answer 3

If you want to find all simple paths, than use modified BFS (you will remember used vertices in order not to repeat them in the path). Finding of all paths might not be even possible (the procedure will not terminate (i.e. it is not an algorithm)). Just imagine graph with cycle, there are infinite paths between all nodes (differing in number of loops contained...)

Answer 4

You can not easily modify Dijkstra to show you all the possible paths. You need to modify the BFS or DFS search.

If you try to modify Dijkstra, in the end, you will end with a BFS or DFS search algorithm, so best start from there instead.

Answer 5

Here are a couple algorithms I found online for finding all possible paths in a graph. They don't modify Dijkstra's algorithm, but I think they should do what you want anyway.

---

From https://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph :

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has m edges, n nodes, and p paths from the source s to the target t, then the algorithm below prints all paths in time O((np+1)(m+n)). (In particular, it takes O(m+n) time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends Ω(n!) time even if p=1: The node t has only one adjacent edge and its neighbor is node s, which is part of a complete (sub)graph Kn−1.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    push y on the path
    search(y)
    pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

---

From All possible paths in a cyclic undirected graph :

You can find all paths using DFS like |Vlad described. To find which nodes appear in every path, you could just maintain an array of booleans that says whether each node has appeared in every path so far. When your DFS finds a path, go through each vertex not in the path and set the corresponding array value to false. When you are done, only the vertices with values of true will be the ones that appear in every path.

Pseudocode:

int source;
int sink;
int nVerts;
bool inAllPaths[nVerts]; // init to all true
bool visited[nVerts]; // init to all false
stack<int> path; // init empty

bool dfs(int u)
  if (visited[u])
    return;
  if (u == sink)
    for i = 0 to nVerts-1
      if !stack.contains(i)
        inAllPaths[i] = false;
    return true;
  else
    visited[u] = true;
    stack.push(u);
    foreach edge (u, v)
      dfs(v);
    stack.pop();
    visited[u] = false;
    return false;


main()
  dfs(source);
  // inAllPaths contains true at vertices that exist in all paths
  // from source to sink.

However, this algorithm isn't very efficient. For example, in a complete graph of n vertices (all vertices have edges to all others) the number of paths will be n! (n factorial).

A better algorithm would be to check for the existence in every path of each vertex separately. For each vertex, try to find a path from the source to the sink without going to that vertex. If you can't find one, that's because the vertex appears in every path.

Pseudocode:

// Using the same initialisation as above, but with a slight modification
// to dfs: change the foreach loop to
foreach edge (u, v)
  if (dfs(v))
    return true; // exit as soon as we find a path

main()
  for i = 0 to nVerts-1
    set all visited to false;
    if (inAllPaths[i])
      visited[i] = true;
      if (dfs(source))
        inAllPaths[i] = false;
      visited[i] = false;

Unfortunately, this still has exponential worst case when searching for a path. You can fix this by changing the search to a breadth-first search. If I'm not mistaken, this should give you O(VE) performance.

---

Some other articles discussing the question:

algorithm to enumerate all possible paths
Find all paths between two graph nodes