How to change dijkstra algorithm to find all possible ways?

Question

I know what one could ask before, but I cannot find him. I need to change below the dijkstra algorithm, which is well suited for finding the shortest path between two nodes, but I also need to find all possible paths. I know that this should be relatively easy to do, but so far I have no idea how to do this the easiest. I use a focused weighted schedule.

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

Well, I really modified the Dijkstra class to make BFS, and it got all the 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 will be as follows:

 Dijkstra d = new Dijkstra(_edges, _nodes); LinkedList<String> visited = new LinkedList<string>(); //collecting all routes visited.AddFirst(start); d.BreadthFirst(graph, visited); 

Answer 2

You cannot easily change Dijkstra to show you all the possible paths. You need to change the search for BFS or DFS.

If you try to change Dijkstra, in the end, you will end the BFS or DFS search algorithm, so it is best to start with this.

Answer 3

If you want to find all the simple ways than using the modified BFS (you will remember that the vertices used are ordered not to repeat them on the way). Finding all paths may not be possible (the procedure will not be completed (i.e., this is not an algorithm)). Imagine a graph with a cycle, there are endless paths between all nodes (different number of cycles contained ...)

Answer 4

Here are a few algorithms that I found on the Internet to search for all possible paths on a chart. They do not change Dijkstra's algorithm, but I think that they should still do what you want.

---

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

Suresh proposed DFS, the MRA indicated that it is not clear what works. Here is my attempt at resolving after this comment stream. If the graph has m edges, n nodes and p paths from source s to the target t, then the algorithm below prints all the paths in time O ((np + 1) (m + n)). (In particular, it takes O (m + n) time to notice that there is no way.)

The idea is very simple: do an exhaustive search, but the guarantee is early if you are in a corner.

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

Press s on the stack stack and search:

 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 the search is exhaustive search and stuck can be implemented in the style of DFS (as here) or in the style of BFS.

---

From All possible paths in a cyclic undirected graph :

You can find all the paths using DFS, as described by Vlad. To find which nodes appear in each path, you can simply save an array of logic elements that says that each node has appeared in each path so far. When your DFS finds a path, go through each vertex out of the path and set the corresponding array value to false. When you're done, only the vertices with true values ​​will be the ones that appear on every path.

pseudo code:

 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 is not very efficient. For example, in a full graph, there are n vertices (all vertices have edges for all others), the number of paths will be n! (n factorial).

The best algorithm would be to check for each vertex in each path separately. For each vertex, try to find the path from the source to the sink without going to that vertex. If you cannot find one, this is because a vertex appears on every path.

pseudo code:

 // 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 the exponential worst case finding path. You can fix this by changing the search to a width search. If I'm not mistaken, this should give you O (VE) performance.

---

Some other articles discussing the issue:

algorithm for listing all possible paths
Find all the paths between two nodes of the graph