Search code examples
algorithmpath-finding

pathfinding: multiple paths to a destination, with edge removal

I have a strange pathfinding problem. In the diagram below, there are two kinds of edges - red and blue. Red edges are reliable, while blue edges are not - they provide shortcuts, but may disappear or be unavailable in some circumstances - you can think of them as mountain passes that get snowed in in winter, or ferry crossings that don't operate on weekends, or train lines that only operate during commuter hours.

I want my pathfinder to produce a selection of possible paths. The user must know the fastest unreliable way to get to their destination, and possible alternatives if that path is not available. The pathfinder should produce the shortest route (in the diagram, 3 hops using blue edge 'b'), and the shortest reliable route - (5 hops, using only red edges) and also all other possible routes that are shorter than the reliable route and make use of the unreliable blue edges.

pathfinding diagram

For the diagram, these are the possible permutations:

  • 3 hops, using edge 'b'
  • 3 hops, using edges 'a', 'd'
  • 4 hops, using edge 'c'
  • 4 hops, using edge 'a'
  • 4 hops, using edge 'd'
  • 5 hops, using only red edges

My first attempt for this algorithm was as follows:

  1. Find & save the shortest possible path (using breadth first search)
  2. If there are no blue edges in the path, stop.
  3. If there are blue edges in the path, remove the first one and go to 1.

However, this algorithm is not complete, as it can miss some possible paths. In the example above, the path using only edge 'a' would be missed (all other paths would be included.)

My next thought was to run a search for every possible combination of blue edges: [a], [b], [c], [d], [a,b], [a,c], ..., [a,b,c,d]. Naturally, this is very inefficient and is probably not viable for large numbers of blue edges.

Can you think of any solutions that could help me out here? I need one of:

  • An efficient way to calculate all the possible paths
  • An algorithm that returns paths in order of shortest to longest

The former is the best solution, but the later I could run for, say, 10 seconds, and then return at least a good selection of short paths to the destination.

Incidentally, I have a pretty good idea of the size of my graph: There are around 7000 vertexes, 30,000 red edges and 200 blue edges.

I'm sure this kind of problem has been considered before, but I can't find anything written about it. Can you point me in the right direction?

Solution

  • As I can see it, you can split your problem into two parts:

    1. Get shortest reliable path - that can be done by removing all blue edges from the graph, and run any shortest path algorithm (such as Dijkstra's Algorithm).
    2. Get k shortest unreliable paths - this is the K shortest paths problem on the unmodified graph, and you will need to chose your k. Bigger k is - more expansive it is going to be to generate the paths.

    Note that finding ALL possible paths is extremely inefficient, since there is factorial number of those, and that number tends to be impossible to calculate in all but the smallest graphs (definetly out of reach for 7,000 nodes)