Package org.graph4j.shortestpath

Class DijkstraShortestPathDefault

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.shortestpath.DijkstraShortestPathBase

org.graph4j.shortestpath.DijkstraShortestPathDefault

All Implemented Interfaces:

SingleSourceShortestPath

public class DijkstraShortestPathDefault
extends DijkstraShortestPathBase

Implementation of Dijkstra's algorithm that iterates through the unsolved vertices in order to select the optimal vertex at each step. The complexity is of O(n^2), where n is the number of vertices. Suitable for dense 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
DijkstraShortestPathDefault(Graph graph, int source)

Method Summary

Modifier and Type	Method	Description
protected int	findMinIndex()

Methods inherited from class org.graph4j.shortestpath.DijkstraShortestPathBase

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

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

DijkstraShortestPathDefault

public DijkstraShortestPathDefault(Graph graph,
 int source)

Method Details

findMinIndex

protected int findMinIndex()

Specified by:

findMinIndex in class DijkstraShortestPathBase