com.kuka.graph.alg
Class Dijkstra<N,E extends Edge<N>>

java.lang.Object
  com.kuka.graph.alg.Dijkstra<N,E>

Type Parameters:

N - The type of the nodes.

E - The type of the edges.

public class Dijkstra<N,E extends Edge<N>>
extends Object

Implements a basic Dijkstra algorithm.

Nested Class Summary

static class

Dijkstra.GoalMode Specifies the termination of the algorithm.

Constructor Summary

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, GraphElementFilter<N> filter)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, N goal)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, N goal, GraphElementFilter<N> filter)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, Set<N> goals)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, Set<N> goals, Dijkstra.GoalMode mode, GraphElementFilter<Edge<N>> edgeFilter)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, Set<N> goals, Dijkstra.GoalMode mode, GraphElementFilter<N> filter, GraphElementFilter<Edge<N>> edgeFilter)
Executes the dijkstra algorithm.

Dijkstra(Graph<N,E> graph, CostFunction<N,E> cost, N start, Set<N> goals, GraphElementFilter<N> filter)
Executes the dijkstra algorithm.

Method Summary

double	cost(N node)
N	getClosestGoal()
Set<N>	getGoals()
Path<N,E>	getShortestPath(N goal) Determines the shortest path to goal, i.e. the path with minimum overall cost from start to goal.

Methods inherited from class java.lang.Object

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

Constructor Detail

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start)

Executes the dijkstra algorithm.

Parameters:

graph - the graph

cost - the cost

start - the start node

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                GraphElementFilter<N> filter)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

filter - the filter specifying whether a node may be traversed or must not be included in the path

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                N goal)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goal - the goal node in the graph

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                N goal,
                GraphElementFilter<N> filter)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goal - the goal node in the graph

filter - the filter specifying whether a node may be traversed or must not be included in the path

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                Set<N> goals,
                GraphElementFilter<N> filter)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goals - the goal nodes in the graph for which the shortest paths shall be computed.

filter - the filter specifying whether a node may be traversed or must not be included in the path

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                Set<N> goals)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goals - the goal nodes in the graph for which the shortest paths shall be computed.

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                Set<N> goals,
                Dijkstra.GoalMode mode,
                GraphElementFilter<Edge<N>> edgeFilter)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goals - the goal nodes in the graph for which the shortest paths shall be computed.

mode - the goal mode (Dijkstra.GoalMode) of the algorithm.

edgeFilter - a filter specifying whether an edge may be traversed or must not be included in the path.

Dijkstra

public Dijkstra(Graph<N,E> graph,
                CostFunction<N,E> cost,
                N start,
                Set<N> goals,
                Dijkstra.GoalMode mode,
                GraphElementFilter<N> filter,
                GraphElementFilter<Edge<N>> edgeFilter)

Executes the dijkstra algorithm.

Parameters:

graph - the graph to find a path in

cost - the function providing information about graph traversal costs

start - the start node in the graph

goals - the goal nodes in the graph for which the shortest paths shall be computed.

mode - the goal mode (Dijkstra.GoalMode) of the algorithm.

filter - the filter specifying whether a node may be traversed or must not be included in the path

edgeFilter - a filter specifying whether an edge may be traversed or must not be included in the path.

Method Detail

getGoals

public Set<N> getGoals()

Returns:

the set of goals that have been found.

getClosestGoal

public N getClosestGoal()

Returns:

the (found) goal node with minimal cost.

getShortestPath

public Path<N,E> getShortestPath(N goal)

Determines the shortest path to goal, i.e. the path with minimum overall cost from start to goal. I no path can be found, the returned path is empty.

Parameters:

goal - the goal node in the graph

Returns:

the shortest path

cost

public double cost(N node)

Parameters:

node - the node for which the cost shall be retrieved.

Returns:

the cost of reaching the node.