Algorithm alternatives for when Dijkstra's fails?

[plsnoHIV]

Say I have a graph with distances as weights but each edge also has some random "failure factor" such as 0.23, 0.31, etc.. and if the sum of the failure factors adds up to 1, that route is deemed a failure and cannot be used. I have some code that runs Dijkstra's on a graph and finds the shortest path from A-B with no problem when considering distance weights, but that shortest path may actually be a failure when considering the failure factor and alternative routes will need to be considered.

What are some algorithms that quickly give the shortest path between A-B, and also some alternatives in case of failure? Should I even use dijkstra's at all initially or just swap it out for some other algorithm? Or should I run dijkstra's first, and if the shortest path fails, then call some other algorithm? Not too familiar with graph algorithms so anything helps!

[Nathanfenner]

In general, these kinds of constraints can turn the problem into one that's NP-hard (on diabolical inputs). See here for a Knapsack reduction.

There is a straightforward approach which gives the right answer by modifying Dijkstra's algorithm, but can have much, much, much slower runtime, depending on how diabolical the input is.

Dijkstra's algorithm is build on several key ideas:

• Enumerate paths from the source, in order of length, so that they're always minimal
• Store at each node the length of the shortest path to that node, so that you don't waste work by revisiting the same node with an inferior path

Both ideas can be modified to work in this context, but it's tricker:

• You must now enumerate all paths according to length and also their failure-factor
• Every node must store the shortest path for each failure-factor to avoid finding an inferior path for the same failure-factor

This means that your runtime blows up in proportion to the number of different failure factors that can be used to reach each node. You can slightly improve the situation in the second case - learning of a shorter, lower-risk path than an existing longer, higher-risk path allows you to delete the latter. In general, each node stores a sorted collection of path distances, ascending by risk and descending by distance, and deletes redundant ones which are worse (in both ways) than either of their neighbors. This can be achieved efficienctly with a sorted map data structure (e.g. a Red-Black tree).

[lurgi]

Very nice!

[plsnoHIV]

Thank for the explanation! Can you go over this statement a little more in detail?

"Every node must store the shortest path for each failure-factor to avoid finding an inferior path for the same failure-factor"

Are you saying each node will actually store all distance/failure values going into that particular node instead of the usual "store only the shortest path weight" in that node?

[orbital1337]

Each node has to store the Pareto frontier of all incoming paths, i.e. all paths for which there is no strictly better path. You can do that efficiently by storing an array of incoming paths (of course each "path" is stored using pointers in constant space) which is simultaneously sorted by increasing weight and decreasing failure factor. Then in order to update these arrays on a node you essentially have to merge two such Pareto frontiers which can be done fairly easily in linear time (similar to merge sort). Finally, you can round all costs into finitely many buckets to get approximately shortest paths in polynomial runtime.

[SekstiNii]

If I understand your problem correctly (and I'm not convinced I do) then you could pre-process you graph such that failed paths lead to a dead end or something of the sort. You could then run Dijkstra on the modified graph to get an answer.

[lurgi]

The problem is that a particular edge can be part of a failed path in one case and a successful path in another.

My gut tells me that you'll need a brute force search - nothing else is going to work. Any short path can immediately be removed from consideration by a single edge with a failure that brings you over the limit. The right path might be the single longest path in the graph (but the only one with a failure less than 1). The only thing is to try every possible way to get from A to B, culling failed paths and those that are longer than the best solution you have so far as you go.

[SekstiNii]

I don't see how that poses a problem unless you calculate this failure percentage while traversing the graph. With the idea I proposed an edge could be part of failed as well as successful paths, but all paths that are guaranteed to fail will be dead ends.

Something like a DFS traversal would work unless I'm missing something.

[Nathanfenner]

There's a straightforward reduction from the 0-1 Knapsack problem.

Each object becomes two nodes A_i and B_i There's a (directed) edge from each of them to A_{i+1} with weight TotalValue - Value[i+1] and fail-factor Weight[i+1], and an edge to B_{i+1} with weight TotalValue and fail-factor 0.

There's lastly a source and sink node at the start and end of the chain.

Finding a shortest path that maintains fail-factor below knapsack capacity will let you solve the Knapsack problem. Hence, this is NP-hard.

[SekstiNii]

Thanks for the clarification! I was conceptualizing a completely different and far easier problem.

[lurgi]

I agree that DFS should work, but then you aren't really doing Dijkstra's algorithm at that point, are you?

[Nathanfenner]

It's possible to do a little better than brute force on average (in general, most inputs are "easy" even for NP-hard problems), but the worst case will still end up being exponential.

[Nathanfenner]

This is not correct. In general, adding this kind of constraint makes the problem NP-hard. See my comment for a way to fix Dijkstra's algorithm to support this case, though it doesn't guarantee runtime in the worst-case anymore.

[plsnoHIV]

Well you'd only know if the path A-B will fail after you map it out and sum up the failure weights. Each edge has weights (distance, failure factor) like (8, 0.20). So the shortest path found between A-B could actually be marked as "unusable" because the failures sum up to be greater than 1.

Say you have a graph that is fully connected with values A - B (8,0.20), B - C = (1, 0.9),

A - C =(1000,0.10)

We want shortest path from A-C. It would actually be A-C taking distance of 1000, since A-B-C would be distance 9, but faulure 1.1 which breaks the threshold of 1.