Package org.graph4j.shortestpath

Class DijkstraShortestPathHeap

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.DijkstraShortestPathBase

org.graph4j.shortestpath.DijkstraShortestPathHeap

All Implemented Interfaces:

SingleSourceShortestPath

public class DijkstraShortestPathHeap
extends DijkstraShortestPathBase

Implementation of Dijkstra's algorithm that uses a heap in order to select the optimal vertex at each step. The complexity of this implementation is O(m log n), where m is the number of edges and n the number of vertices. Suitable for sparse graphs.

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.shortestpath.DijkstraShortestPathBase

before, cost, numSolved, size, solved, source, vertices

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
DijkstraShortestPathHeap(Graph graph, int source)

Method Summary

Modifier and Type	Method	Description
protected int	findMinIndex()
protected void	postUpdate(int index)
protected void	preCompute()

Methods inherited from class org.graph4j.shortestpath.DijkstraShortestPathBase

compute, computePath, createPathEndingIn, findPath, getPathWeight, getPathWeights, getSource

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.graph4j.shortestpath.SingleSourceShortestPath

getGraph

Constructor Details

DijkstraShortestPathHeap

public DijkstraShortestPathHeap(Graph graph,
 int source)

Method Details

preCompute

protected void preCompute()

Overrides:

preCompute in class DijkstraShortestPathBase

postUpdate

protected void postUpdate(int index)

Overrides:

postUpdate in class DijkstraShortestPathBase

findMinIndex

protected int findMinIndex()

Specified by:

findMinIndex in class DijkstraShortestPathBase