Find shortest path between two nodes in directed weighted graph

Question

I have a directed weighted graph G = <V, E>. I need to find shortest path between s and t in O((V + E)*logV). It would be a really simple task, if I have a classical metric weight of path. But it is not.

Weight of path = two heaviest edges in this path.

Therefore, classic Dijkstra's algorithm with modified binary heap does not work. I think, that I have to modify this algorithm. I'm trying to do it, but I have no success.

Example.

Weight of path between 3 and 5 = 4 + 2 = 6

Weight of path between 3 and 7 = 4 + 4 = 8

Answer 1

Edited my answer based on counter example by David Eisenstat.

The example you give in your question is not a good example of when Dijkstra will not work.

I believe you can do this by modifying Dijkstra. The key is to keep track of multiple alternatives for each Vertex. Not only do you have to store the weigths that make up the shortest path, you also have to store alternatives where max < shortest.max and min > shortest.min.

Dijkstra is greedy, so what you have to figure out is: is it possible that once a shortest path is determined, another path can be found that turns out to be shorter. Because you will discover paths in increasing length, this is not possible.