I am looking into a problem of finding the shortest/longest paths in a graph with weighted edges (i.e. edges having length). The typical approaches are Belmann-Ford, Floyd-Warshall, and Dijkstra algorithms, which allow for significantly accelerated search (as compared to enumerating all the paths).
I am interested in the generalizations of the above algorithms to the following cases:
- Finding suboptimal paths, i.e. not only the shortest path between two points, but the second shortest path, the third shortest path, etc.
- Finding the shortest/longest paths in a multigraph with parallel edges of different length
- Combination of the two.
Regarding (2) I suppose that one could reduce the graph by choosing the shortest/longest branch between every pair of nodes and then apply the above mentioned algorithms. However, this approach would not work for (3).