Efficient algorithm to find all the paths from A to Z?

Question

With a set of random inputs like this (20k lines):

A B
U Z
B A
A C
Z A
K Z
A Q
D A
U K
P U
U P
B Y
Y R
Y U
C R
R Q
A D
Q Z

Find all the paths from A to Z.

1. A - B - Y - R - Q - Z
2. A - B - Y - U - Z
3. A - C - R - Q - Z
4. A - Q - Z
5. A - B - Y - U - K - Z

A location cannot appear more than once in the path, hence A - B - Y - U - P - U - Z is not valid.

Locations are named AAA to ZZZ (presented here as A - Z for simplicity) and the input is random in such a way that there may or may not be a location ABC, all locations may be XXX (unlikely), or there may not be a possible path at all locations are "isolated".

Initially I'd thought that this is a variation of the unweighted shortest path problem, but I find it rather different and I'm not sure how does the algorithm there apply here.

My current solution goes like this:

1. Pre-process the list such that we have a hashmap which points a location (left), to a list of locations (right)

2. Create a hashmap to keep track of "visited locations". Create a list to store "found paths".

3. Store X (starting-location) to the "visited locations" hashmap.

4. Search for X in the first hashmap, (Location A will give us (B, C, Q) in O(1) time).

5. For-each found location (B, C, Q), check if it is the final destination (Z). If so store it in the "found paths" list. Else if it doesn't already exist in "visited locations" hashmap, Recurl to step 3 now with that location as "X". (actual code below)

With this current solution, it takes forever to map all (not shortest) possible routes from "BKI" to "SIN" for this provided data.

I was wondering if there's a more effective (time-wise) way of doing it. Does anyone know of a better algorithm to find all the paths from an arbitrary position A to an arbitrary position Z ?

Actual Code for current solution:

import java.util.*;
import java.io.*;

public class Test {
    private static HashMap<String, List<String>> left_map_rights;

    public static void main(String args[]) throws Exception {
        left_map_rights = new HashMap<>();
        BufferedReader r = new BufferedReader(new FileReader("routes.text"));
        String line;
        HashMap<String, Void> lines = new HashMap<>();
        while ((line = r.readLine()) != null) {
            if (lines.containsKey(line)) { // ensure no duplicate lines
                continue;
            }
            lines.put(line, null);
            int space_location = line.indexOf(' ');
            String left = line.substring(0, space_location);
            String right = line.substring(space_location + 1);
            if(left.equals(right)){ // rejects entries whereby left = right
                continue;
            }
            List<String> rights = left_map_rights.get(left);
            if (rights == null) {
                rights = new ArrayList<String>();
                left_map_rights.put(left, rights);
            }
            rights.add(right);
        }
        r.close();
        System.out.println("start");
        List<List<String>> routes = GetAllRoutes("BKI", "SIN");
        System.out.println("end");
        for (List<String> route : routes) {
            System.out.println(route);
        }
    }

    public static List<List<String>> GetAllRoutes(String start, String end) {
        List<List<String>> routes = new ArrayList<>();
        List<String> rights = left_map_rights.get(start);
        if (rights != null) {
            for (String right : rights) {
                List<String> route = new ArrayList<>();
                route.add(start);
                route.add(right);
                Chain(routes, route, right, end);
            }
        }
        return routes;
    }

    public static void Chain(List<List<String>> routes, List<String> route, String right_most_currently, String end) {
        if (right_most_currently.equals(end)) {
            routes.add(route);
            return;
        }
        List<String> rights = left_map_rights.get(right_most_currently);
        if (rights != null) {
            for (String right : rights) {
                if (!route.contains(right)) {
                    List<String> new_route = new ArrayList<String>(route);
                    new_route.add(right);
                    Chain(routes, new_route, right, end);
                }
            }
        }
    }
}

Answer 1

As I understand your question, Dijkstras algorithm cannot be applied as is, since shortest path problem per definition finds a single path in a set of all possible paths. Your task is to find all paths per-se.

Many optimizations on Dijkstras algorithm involve cutting off search trees with higher costs. You won't be able to cut off those parts in your search, as you need all findings.

And I assume you mean all paths excluding circles.

Algorithm:

• Pump network into a 2dim array 26x26 of boolean/integer. fromTo[i,j]. Set a 1/true for an existing link.

• Starting from the first node trace all following nodes (search links for 1/true).

• Keep visited nodes in a some structure (array/list). Since maximal depth seems to be 26, this should be possible via recursion.

• And as @soulcheck has written below, you may think about cutting of paths you have aleady visted. You may keep a list of paths towards the destination in each element of the array. Adjust the breaking condition accordingly.

• Break when

  • visiting the end node (store the result)
  • when visiting a node that has been visted before (circle)
  • visiting a node for which you have already found all paths to the destination and merge your current path with all the existing ones from that node.

Performance wise I'd vote against using hashmaps and lists and prefer static structures.

Hmm, while re-reading the question, I realized that the name of the nodes cannot be limited to A-Z. You are writing something about 20k lines, with 26 letters, a fully connected A-Z network would require far less links. Maybe you skip recursion and static structures :)

Ok, with valid names from AAA to ZZZ an array would become far too large. So you better create a dynamic structure for the network as well. Counter question: regarding performance, what is the best data structure for a less popuplate array as my algorithm would require? I' vote for an 2 dim ArrayList. Anyone?

Answer 2

What you're proposing is a scheme for DFS, only with backtracking.It's correct, unless you want to permit cyclic paths (you didn't specify if you do).

There are two gotchas, though.

1. You have to keep an eye on nodes you already visited on current path (to eliminate cycles)
2. You have to know how to select next node when backtracking, so that you don't descend on the same subtree in the graph when you already visited it on the current path.

The pseudocode is more or less as follows:

getPaths(A, current_path) :
    if (A is destination node): return [current_path]
    for B = next-not-visited-neighbor(A) : 
        if (not B already on current path) 
            result = result + getPaths(B, current_path + B)
    return result 

 list_of_paths =  getPaths(A, [A])

which is almost what you said.

Be careful though, as finding all paths in complete graph is pretty time and memory consuming.

edit For clarification, the algorithm has Ω(n!) time complexity in worst case, as it has to list all paths from one vertex to another in complete graph of size n, and there are at least (n-2)! paths of form <A, permutations of all nodes except A and Z, Z>. No way to make it better if only listing the result would take as much.