Package com.jgalgo.alg.shortestpath

Interface KShortestPathsSt

All Known Implementing Classes:
KShortestPathsStAbstract, KShortestPathsStBasedPathsTree, KShortestPathsStHershbergerMaxelSuri, KShortestPathsStKatohIbarakiMine, KShortestPathsStYen
public interface KShortestPathsSt
An algorithm for computing the K shortest paths between two vertices in a graph.

Given a graph \(G=(V,E)\), and a weight function \(w:E \rightarrow R\), one might ask what are the K shortest paths from a source vertex to a target vertex, where the 'shortest' is defined by comparing the sum of edges weights of each path. This interface computes such paths. It differ from ShortestPathSt, as it computes multiple paths, and not just one.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    <V, E> List<Path<V,E>>
    computeKShortestPaths(Graph<V,E> g, WeightFunction<E> w, V source, V target, int k)
    Compute the K shortest paths from a source vertex to a target vertex.
    static KShortestPathsSt
    newInstance()
    Create a new K shortest paths algorithm object.

  • Method Details

    • computeKShortestPaths

      <V, E> List<Path<V,E>> computeKShortestPaths(Graph<V,E> g, WeightFunction<E> w, V source, V target, int k)
      Compute the K shortest paths from a source vertex to a target vertex.

      If g is IntGraph, the returned object is a list of IPath. If g is IntGraph, prefer to pass IWeightFunction for best performance.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      w - an edge weight function
      source - the source vertex
      target - the target vertex
      k - the number of shortest paths to compute
      Returns:
      k shortest paths from the source to the target, or less if there are no such k paths

    • newInstance

      static KShortestPathsSt newInstance()
      Create a new K shortest paths algorithm object.

      This is the recommended way to instantiate a new KShortestPathsSt object.

      Returns:
      a default implementation of KShortestPathsSt