Generalization of the longest/shortest path algorithms (Bellman-Ford, Floyd-Warshall, Dijkstra)

353 views Asked by At

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:

  1. Finding suboptimal paths, i.e. not only the shortest path between two points, but the second shortest path, the third shortest path, etc.
  2. Finding the shortest/longest paths in a multigraph with parallel edges of different length
  3. 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).

0

There are 0 answers