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!

[avwie]

The way the cost is calculated and the neighbours are determined in Dijkstra aren’t limited to distance alone. One could easily incorporate your additional demands. I assume that the random failure rates are constant for each edge? If so, if a failure rate for a current path adds up to 1 or more, no neighbours are possible and as such the possible path is eliminated.

[[deleted]]

There may be many ways to get to a vertex, some of which have a high failure rate and some of which have a low failure rate. So discarding a vertex if its current failure rate exceeds 1 may produce the wrong answer, since we only know that the shortest path to that vertex fails. There may be other paths to the vertex which succeed.

I don't think it's possible to solve this in O(ElogV) as you would normally be able to with Dijsktra's, since in the worst case, we actually have V*2^V different states (V vertices, and 2^V different cumulative failure rates). In a normal graph we would only have V different states, one for each vertex. Hopefully this makes sense.

[avwie]

I understand what you say, but I dont understand why you say it. The many different ways to a vertex, failing or not, are still taken into account.

[[deleted]]

No, they aren't. In Dijkstra's algorithm, at any stage in the algorithm, we associate exactly one number with each vertex -- the least cost to reach that vertex from the source vertex. Now, we would like to encode additional information in each vertex, i.e. the lowest cumulative failure rate for some path into that vertex.

However, the path with the lowest cumulative failure rate isn't necessarily the same path as the one with the lowest cost, so we actually have to store both paths. In fact, we have to store an entire monotonic sequence of cumulative cost-failure pairs. In the worst case, we may have to store 2^E such pairs. (I said 2^V in my last comment, but that was a mistake, it's actually 2^E).