Class SuurballeKDisjointShortestPaths<V,E>

Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:

public class SuurballeKDisjointShortestPaths<V,E> extends Object
An implementation of Suurballe algorithm for finding K edge-disjoint shortest paths. The algorithm determines the k disjoint shortest simple paths in increasing order of weight. Only directed simple graphs are allowed.

The algorithm is running k sequential Dijkstra iterations to find the shortest path at each step. Hence, yielding a complexity of k*O(Dijkstra).

For further reference see Wikipedia page

  • Suurballe, J. W.; Tarjan, R. E. (1984), A quick method for finding shortest pairs of disjoint paths.
Assaf Mizrachi
  • Field Details

    • workingGraph

      protected Graph<V,E> workingGraph
      Graph on which shortest paths are searched.
    • pathList

      protected List<List<E>> pathList
    • originalGraph

      protected Graph<V,E> originalGraph
  • Constructor Details

  • Method Details

    • transformGraph

      protected void transformGraph(List<E> previousPath)
      Prepares the working graph for next iteration. To be called from the second iteration and on so implementation may assume a preceding calculateShortestPath(V, V) call.
      previousPath - the path found at the previous iteration.
    • calculateShortestPath

      protected GraphPath<V,E> calculateShortestPath(V startVertex, V endVertex)
      Calculates the shortest paths for the current iteration. Path is not final; rather, it is intended to be used in a "post-production" phase (see resolvePaths method).
      startVertex - the start vertex
      endVertex - the end vertex
      the shortest path between start and end vertices.
    • getPaths

      public List<GraphPath<V,E>> getPaths(V startVertex, V endVertex, int k)
      Returns the $k$ shortest simple paths in increasing order of weight.
      Specified by:
      getPaths in interface KShortestPathAlgorithm<V,E>
      startVertex - source vertex of the calculated paths.
      endVertex - target vertex of the calculated paths.
      k - the number of shortest paths to return
      list of disjoint paths between the start vertex and the end vertex
      IllegalArgumentException - if the graph does not contain the startVertex or the endVertex
      IllegalArgumentException - if the startVertex and the endVertex are the same vertices
      IllegalArgumentException - if the startVertex or the endVertex is null