11

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"]); }
Improve this question
2
  • I have edited your title. Please see, "Should questions include “tags” in their titles?", where the consensus is "no, they should not". Commented Apr 14, 2013 at 18:58
  • do you know how this algorithm works? Once you do, it is much easier to find how to change it, to return all possible paths. Commented Apr 14, 2013 at 19:21

5 Answers 5

Reset to default
4

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);
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

You helped a lot Zulu. I was able to adapt your code to my existing code need. Thanks much! :) Keep sharing man...
I am commenting on a very old post, but a quick basic question. In your modified new method - BreadthFirst, does the graph variable hold the adjacency list nodes? If I am understanding this correctly, then graph.adjacentNodes(visited.Last()) will simply give all the nodes adjacent to the current node, as provided by the adjacency list representation. If yes, then what does this method gain from the Dijkstra's algorithm? The input seems to be the adjacency graph and not the Dijkstra's output, if I am not overlooking something?
2

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.

Improve this answer

1 Comment

Well, in code part below I have all possibles routes between neigbours in Dist[] but the program takes of curse the smallest one so I was thinking that maybe in here some clever trick could do the job. 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;
1

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...)

Improve this answer

Comments

0

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

Improve this answer

Comments

0

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:

enter image description here

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.