Package com.jgalgo.alg.shortestpath

Class VoronoiAlgoDijkstra

java.lang.Object
com.jgalgo.alg.shortestpath.VoronoiAlgoAbstract
com.jgalgo.alg.shortestpath.VoronoiAlgoDijkstra
All Implemented Interfaces:
VoronoiAlgo
public class VoronoiAlgoDijkstra extends VoronoiAlgoAbstract
Variant of Dijkstra algorithm that starts at multiple vertices and compute the Voronoi cells.

The algorithm uses a variant of Dijkstra's shortest path algorithm that grows a forest rooted at the given site vertices, rather than a single tree rooted at a source vertex. This can also be achieved by a reduction to the single source variant: create a new graph identical to the input graph, and add an additional auxiliary vertex connected to all the site vertices with zero weight edges, than compute the shortest path tree for the new vertex. This approach runs in the same asymptotic complexity, but suffer for the real world additional work of creating a new graph.

The overall running time of this algorithm is \(O(m + n \log n)\) and it uses a linear space, same as the single source Dijkstra algorithm.

Author:
Barak Ugav

  • Constructor Details

    • VoronoiAlgoDijkstra

      public VoronoiAlgoDijkstra()
      Create a algorithm for computing the Voronoi cells in a graph.

      Please prefer using VoronoiAlgo.newInstance() to get a default implementation for the VoronoiAlgo interface.