Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The two paths can have some shared edges. I thought about storing for each vertex two fathers, and trying to build the second path from those fields, but I'm not sure how I can guarantee that I will create the desirable path. The implementation should stand in Dijkstra time complexity.

Any suggestions?