
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.ShortestPaths
public class ShortestPaths
This class provides diverse algorithms and helper methods for solving the shortest path problem on weighted graphs.
Given a weighted directed/undirected graph:
s
and a target node t
such that the sum of the edge costs is minimized.k
shortest paths between a source
node s
and a target node t
such that the sum of the edge costs is minimized.s
to all other nodes such that the sum of the edge costs is minimized.s
to a target node t
such that the sum of the edge costs is
minimized.
Method Summary  

static boolean 
acyclic(Graph graph,
Node s,
DataProvider cost,
NodeMap dist,
NodeMap pred)
Like acyclic(Graph, Node, double[], double[]) but uses NodeMap s and
DataProvider s instead of arrays. 
static boolean 
acyclic(Graph graph,
Node s,
double[] cost,
double[] dist)
Solves the singlesource shortest path problem for acyclic directed graphs. 
static boolean 
acyclic(Graph graph,
Node s,
double[] cost,
double[] dist,
Edge[] pred)
Like acyclic(Graph, Node, double[], double[]) but, additionally, this method
yields the path edges of each calculated shortest path. 
static boolean 
allPairs(Graph graph,
boolean directed,
double[] cost,
double[][] dist)
This method solves the allpairs shortest path problem for graphs with arbitrary edge costs. 
static EdgeList 
aStar(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost,
DataProvider heuristicCost)
Solves the singlesource singlesink shortest path problem for arbitrary graphs using an implementation of the wellknown astar algorithm (A*). 
static double 
aStar(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost,
DataProvider heuristicCost,
NodeMap pred)
Solves the singlesource singlesink shortest path problem for arbitrary graphs using an implementation of the wellknown astar algorithm (A*). 
static EdgeList 
aStar(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost,
double[] heuristicCost)
Solves the singlesource singlesink shortest path problem for arbitrary graphs using an implementation of the wellknown astar algorithm (A*). 
static double 
aStar(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost,
double[] heuristicCost,
Edge[] pred)
Solves the singlesource singlesink shortest path problem for arbitrary graphs using an implementation of the wellknown astar algorithm (A*). 
static boolean 
bellmanFord(Graph graph,
Node s,
boolean directed,
DataProvider cost,
NodeMap dist,
NodeMap pred)
Like bellmanFord(Graph, Node, boolean, double[], double[], Edge[])
but uses NodeMap s and DataProvider s instead of arrays. 
static boolean 
bellmanFord(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist)
Solves the singlesource shortest path problem for arbitrary graphs. 
static boolean 
bellmanFord(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist,
Edge[] pred)
Like bellmanFord(Graph, Node, boolean, double[], double[]) but, additionally, this method
yields the path edges of each calculated shortest path. 
static EdgeList 
constructEdgePath(Node s,
Node t,
DataProvider pred)
Like constructEdgePath(Node, Node, Edge[]) but the path edges are given by a DataProvider . 
static EdgeList 
constructEdgePath(Node s,
Node t,
Edge[] pred)
Convenience method that constructs an explicit path of edges from the
result returned by one of the shortest paths methods defined in this class. 
static NodeList 
constructNodePath(Node s,
Node t,
DataProvider pred)
Like constructNodePath(Node, Node, Edge[]) but the path edges are given by a DataProvider . 
static NodeList 
constructNodePath(Node s,
Node t,
Edge[] pred)
Convenience method that constructs an explicit path of nodes from the
result returned by one of the shortest paths methods defined in this class. 
static void 
dijkstra(Graph graph,
Node s,
boolean directed,
DataProvider cost,
NodeMap dist,
NodeMap pred)
Like dijkstra(Graph, Node, boolean, double[], double[]) but uses NodeMap s and
DataProvider s instead of arrays. 
static void 
dijkstra(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist)
Solves the singlesource shortest path problem for arbitrary graphs. 
static void 
dijkstra(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist,
Edge[] pred)
Like dijkstra(Graph, Node, boolean, double[], double[]) but, additionally, this method
yields the path edges of each calculated shortest path. 
static void 
findShortestUniformPaths(Graph graph,
Node start,
DataProvider targetMap,
boolean directed,
int maxLength,
EdgeList pathEdges,
NodeList pathNodes)
Finds all nodes and edges that belong to a shortest path from a start node to a set of target nodes
in the graph not farther away than a given distance. 
static void 
findShortestUniformPaths(Graph graph,
Node start,
Node end,
boolean directed,
EdgeMap pathMap)
Marks all edges that belong to a shortest path from start node to target node. 
static YList 
kShortestPaths(Graph graph,
DataProvider costDP,
Node start,
Node end,
int k)
This method finds the k shortest paths connecting a pair of nodes in a directed graph with
nonnegative edge costs. 
static YCursor 
kShortestPathsCursor(Graph graph,
DataProvider costDP,
Node start,
Node end,
int k)
A variant of kShortestPaths(Graph, DataProvider, Node, Node, int)
that returns the result as a special cursor that calculates
the next path in the sequence only when needed. 
static EdgeList[] 
shortestPair(Graph graph,
Node source,
Node target,
boolean directed,
DataProvider costDP)
Returns two edgedisjoint paths in a nonnegatively weighted directed graph, such that both paths connect nodes s and t and have minimum total length. 
static boolean 
singleSource(Graph graph,
Node s,
boolean directed,
DataProvider cost,
NodeMap dist,
NodeMap pred)
Like singleSource(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMap s and
DataProvider s instead of arrays. 
static boolean 
singleSource(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist)
This method solves the singlesource shortest path problem for arbitrary graphs. 
static boolean 
singleSource(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist,
Edge[] pred)
Like singleSource(Graph, Node, boolean, double[], double[]) but, additionally, this method
yields the path edges of each calculated shortest path. 
static EdgeList 
singleSourceSingleSink(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost)
Similar to singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap) but instead of returning
the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. 
static double 
singleSourceSingleSink(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost,
NodeMap pred)
Like singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but uses NodeMap s and
DataProvider s instead of arrays. 
static EdgeList 
singleSourceSingleSink(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost)
Similar to singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[]) but instead of returning
the shortest distance between the source and sink the actual shortest edge path between these nodes will be
returned. 
static double 
singleSourceSingleSink(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost,
Edge[] pred)
This method solves the singlesource singlesink shortest path problem for arbitrary graphs. 
static void 
uniform(Graph graph,
Node s,
boolean directed,
double[] dist)
Solves the singlesource shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0 . 
static void 
uniform(Graph graph,
Node s,
boolean directed,
double[] dist,
Edge[] pred)
Like uniform(Graph, Node, boolean, double[]) but, additionally, yields the edges of each calculated
shortest path. 
static void 
uniform(Graph graph,
Node s,
boolean directed,
NodeMap dist,
NodeMap pred)
Like uniform(Graph, Node, boolean, double[]) but uses NodeMap s instead of arrays. 
static double[] 
uniformCost(Graph graph)
Convenience method that returns an array containing uniform edge costs of 1.0 for each edge of the
given graph. 
Methods inherited from class java.lang.Object 

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

public static void uniform(Graph graph, Node s, boolean directed, double[] dist)
1.0
.
This method yields the shortest distance from a given node s
to all other nodes.
dist.length == graph.N()
O(graph.N() + graph.E())
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisedist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.public static void uniform(Graph graph, Node s, boolean directed, double[] dist, Edge[] pred)
uniform(Graph, Node, boolean, double[])
but, additionally, yields the edges of each calculated
shortest path.
pred.length == graph.N()
O(graph.N() + graph.E())
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisedist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the
shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.uniform(Graph, Node, boolean, double[])
,
constructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
public static void uniform(Graph graph, Node s, boolean directed, NodeMap dist, NodeMap pred)
uniform(Graph, Node, boolean, double[])
but uses NodeMap
s instead of arrays.
pred.length == graph.N()
O(graph.N() + graph.E())
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisedist
 the NodeMap
that will be filled during the execution and returns a double value (shortest distance)
from node s
to all other nodes or Double.POSITIVE_INFINITY
if no such paths existpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if t == s
or no
shortest path from s
to t
existsuniform(Graph, Node, boolean, double[])
,
constructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
public static boolean acyclic(Graph graph, Node s, double[] cost, double[] dist)
Each edge is associated with an arbitrary double value that represents the cost of that edge.
This method yields the shortest distance from a given node s
to all other nodes.
acyclic
.cost.length == graph.E()
dist.length == graph.N()
O(graph.N() + graph.E())
graph
 the input graphs
 the node from which the shortest path search startscost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.
true
if the input graph is acyclic, false
otherwiseacyclic(Graph, Node, double[], double[], Edge[])
,
acyclic(Graph, Node, DataProvider, NodeMap, NodeMap)
public static boolean acyclic(Graph graph, Node s, double[] cost, double[] dist, Edge[] pred)
acyclic(Graph, Node, double[], double[])
but, additionally, this method
yields the path edges of each calculated shortest path.
Each edge is associated with an arbitrary double value that represents the cost of that edge.
This method yields the shortest distance from a given node s
to all other nodes.
pred.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startscost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the
shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
true
if the input graph is acyclic, false
otherwiseacyclic(Graph, Node, double[], double[])
,
acyclic(Graph, Node, double[], double[], Edge[])
,
constructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
public static boolean acyclic(Graph graph, Node s, DataProvider cost, NodeMap dist, NodeMap pred)
acyclic(Graph, Node, double[], double[])
but uses NodeMap
s and
DataProvider
s instead of arrays.
Each edge is associated with an arbitrary double value that represents the cost of that edge.
This method yields the shortest distance from a given node s
to all other nodes.
pred.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startscost
 the DataProvider
that returns the double value (cost) for traversing each edgedist
 the NodeMap
that will be filled during the execution and returns a double value (shortest distance)
from node s
to all other nodes or Double.POSITIVE_INFINITY
if no such paths existpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if t == s
or no
shortest path from s
to t
exists
true
if the input graph is acyclic, false
otherwiseacyclic(Graph, Node, double[], double[])
,
acyclic(Graph, Node, double[], double[], Edge[])
public static EdgeList aStar(Graph graph, Node s, Node t, boolean directed, double[] cost, double[] heuristicCost)
Each edge is associated with a nonnegative double value that represents the cost of the edge. The costs should be nonnegative.
Furthermore, the algorithm uses socalled heuristic costs for each node. The heuristic
cost for a node n
is the estimated cost to reach the sink node t
from n
.
The heuristic has a crucial impact on the performance of the shortest path search:
dijkstra(Graph, Node, Node, boolean, double[], Edge[])
if you have no
proper problemspecific heuristic.
cost.length == graph.E()
heuristicCost.length == graph.N()
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that represent the costs for traversing each edge; edge e
has cost cost[e.index()]
heuristicCost
 an array of double values that represent an estimate to reach the sink node t
.
The value of heuristicCost[n.index()]
is the estimated heuristic cost
to reach node t
from node n
s
to the sink node t
or an empty list if there is no such pathaStar(Graph, Node, Node, boolean, DataProvider, DataProvider)
,
aStar(Graph, Node, Node, boolean, double[], double[], Edge[])
,
aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)
public static EdgeList aStar(Graph graph, Node s, Node t, boolean directed, DataProvider cost, DataProvider heuristicCost)
This method is like aStar(Graph, Node, Node, boolean, double[], double[])
, with the only
difference that it takes DataProvider
s as parameters instead of arrays.
Each edge is associated with a nonnegative double value that represents the cost of the edge. The costs should be nonnegative.
Furthermore, the algorithm uses socalled heuristic costs for each node. The heuristic
cost for a node n
is the estimated cost to reach the sink node t
from n
.
The heuristic has a crucial impact on the performance of the shortest path search:
dijkstra(Graph, Node, boolean, double[], double[], Edge[])
if you have no
proper problemspecific heuristic.
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the cost for traversing an edgeheuristicCost
 the DataProvider
that yields for each node the heuristic cost estimate to reach the
sink node t
starting from the node
s
to the sink node t
or an empty list if there is no such pathaStar(Graph, Node, Node, boolean, double[], double[])
,
aStar(Graph, Node, Node, boolean, double[], double[], Edge[])
,
aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)
public static double aStar(Graph graph, Node s, Node t, boolean directed, double[] cost, double[] heuristicCost, Edge[] pred)
This method is like aStar(Graph, Node, Node, boolean, double[], double[])
, with the
difference that it does not return the shortest path but the cost of the shortest path. To construct
the actual shortest path use constructEdgePath(Node, Node, Edge[])
or constructNodePath(Node, Node, Edge[])
.
Each edge is associated with a nonnegative double value that represents the cost of the edge. The costs should be nonnegative.
Furthermore, the algorithm uses socalled heuristic costs for each node. The heuristic
cost for a node n
is the estimated cost to reach the sink node t
from n
.
The heuristic has a crucial impact on the performance of the shortest path search:
dijkstra(Graph, Node, boolean, double[], double[], Edge[])
if you have no
proper problemspecific heuristic.
cost.length == graph.E()
heuristicCost.length == graph.N()
pred.length == graph.N()
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that represent the costs for traversing each edge; edge e
has cost cost[e.index()]
heuristicCost
 an array of double values that represent an estimate to reach the sink node t
.
The value of heuristicCost[n.index()]
is the estimated heuristic cost
to reach node t
from node n
pred
 an array of Edge
s that will be filled during the execution and holds for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
s
and t
if a path between these two
nodes exists or Double.POSITIVE_INFINITY
otherwiseaStar(Graph, Node, Node, boolean, double[], double[])
,
aStar(Graph, Node, Node, boolean, DataProvider, DataProvider)
,
aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)
public static double aStar(Graph graph, Node s, Node t, boolean directed, DataProvider cost, DataProvider heuristicCost, NodeMap pred)
This method is like aStar(Graph, Node, Node, boolean, double[], double[], Edge[])
, with the only
difference that it takes DataProvider
s and a NodeMap
as input instead of arrays.
Each edge is associated with a nonnegative double value that represents the cost of the edge. The costs should be nonnegative.
Furthermore, the algorithm uses socalled heuristic costs for each node. The heuristic
cost for a node n
is the estimated cost to reach the sink node t
from n
.
The heuristic has a crucial impact on the performance of the shortest path search:
dijkstra(Graph, Node, boolean, double[], double[], Edge[])
if you have no
proper problemspecific heuristic.
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the cost for traversing an edgeheuristicCost
 the DataProvider
that yields for each node the heuristic cost estimate to reach the
sink node t
starting from the nodepred
 the map that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
s
and t
if a path between these two
nodes exists or Double.POSITIVE_INFINITY
otherwiseaStar(Graph, Node, Node, boolean, double[], double[])
,
aStar(Graph, Node, Node, boolean, DataProvider, DataProvider)
,
aStar(Graph, Node, Node, boolean, double[], double[], Edge[])
public static void dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
Each edge is associated with a nonnegative double value that represents the cost of the edge.
This method yields the shortest distance from a given node s
to all other nodes.
The costs should be nonnegative.
cost.length == graph.E()
dist.length == graph.N()
O(graph.E() + graph.N() * log(graph.N())
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.dijkstra(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
,
dijkstra(Graph, Node, boolean, double[], double[], Edge[])
public static void dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
dijkstra(Graph, Node, boolean, double[], double[])
but, additionally, this method
yields the path edges of each calculated shortest path.
Each edge is associated with a nonnegative double value that represents the cost of the edge.
This method yields the shortest distance from a given node s
to all other nodes.
The costs should be nonnegative.
pred.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.constructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
dijkstra(Graph, Node, boolean, double[], double[])
,
dijkstra(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
public static void dijkstra(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
dijkstra(Graph, Node, boolean, double[], double[])
but uses NodeMap
s and
DataProvider
s instead of arrays.
Each edge is associated with a nonnegative double value that represents the cost of the edge.
This method yields the shortest distance from a given node s
to all other nodes.
The costs should be nonnegative.
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the double value (cost) for traversing each edgedist
 the NodeMap
that will be filled during the execution and returns a double value (shortest distance)
from node s
to all other nodes or Double.POSITIVE_INFINITY
if no such paths existpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
existsconstructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
dijkstra(Graph, Node, boolean, double[], double[])
,
dijkstra(Graph, Node, boolean, double[], double[], Edge[])
public static double singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, double[] cost, Edge[] pred)
Each edge is associated with a nonnegative double value that represents the cost of the edge.
This method returns the shortest distance from node s
to node t
. It also returns
information to construct the actual path between these two nodes.
The costs should be nonnegative.
cost.length == graph.E()
pred.length == graph.N()
O(graph.E() + graph.N() * log(graph.N())
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
s
and t
if a path between these two
nodes exists or Double.POSITIVE_INFINITY
otherwiseconstructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider)
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)
,
singleSourceSingleSink(Graph, Node, Node, boolean, double[])
public static EdgeList singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, double[] cost)
singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])
but instead of returning
the shortest distance between the source and sink the actual shortest edge path between these nodes will be
returned.
Each edge is associated with a nonnegative double value that represents the cost of the edge.
If the returned path is empty, then there is no path between the nodes.
The costs should be nonnegative.
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
path of edges
between source and sinksingleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider)
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)
public static EdgeList singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, DataProvider cost)
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)
but instead of returning
the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.
Each edge is associated with a nonnegative double value that represents the cost of the edge.
If the returned path is empty, then there is no path between the nodes.
The costs should be nonnegative.
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the double value (cost) for traversing each edge
path of edges
between source and sinksingleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)
,
singleSourceSingleSink(Graph, Node, Node, boolean, double[])
public static double singleSourceSingleSink(Graph graph, Node s, Node t, boolean directed, DataProvider cost, NodeMap pred)
singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])
but uses NodeMap
s and
DataProvider
s instead of arrays.
Each edge is associated with a nonnegative double value that represents the cost of the edge.
The costs should be nonnegative.
graph
 the input graphs
 the source nodet
 the sink nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the double value (cost) for traversing each edgepred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
s
and t
if a path between these two
nodes exists or Double.POSITIVE_INFINITY
otherwisesingleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])
,
singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider)
,
singleSourceSingleSink(Graph, Node, Node, boolean, double[])
public static boolean bellmanFord(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
Each edge is associated with an arbitrary double value that represents the cost of this edge.
In case the given weighted graph contains no negative cost cycles, this method will yield the shortest
distance from a given node s
to all other nodes. If, on the other hand, the given graph contains
negativecost cycles, this method will yield no reasonable result which will be indicated by the
return value false
.
cost.length == graph.E()
dist.length == graph.N()
O(graph.E() * min(D, graph.N()))
, where D
is the maximum
number of edges in any shortest pathgraph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.
true
if the algorithm found a valid result,
false
otherwise (i.e., graph contains negativecost cycles)bellmanFord(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
,
bellmanFord(Graph, Node, boolean, double[], double[], Edge[])
public static boolean bellmanFord(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
bellmanFord(Graph, Node, boolean, double[], double[])
but, additionally, this method
yields the path edges of each calculated shortest path.
Each edge is associated with an arbitrary double value that represents the cost of this edge.
In case the given weighted graph contains no negative cost cycles, this method will yield the shortest
distance from a given node s
to all other nodes. If, on the other hand, the given graph contains
negativecost cycles, this method will yield no reasonable result which will be indicated by the
return value false
.
pred.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
true
if the algorithm found a valid result,
false
otherwise (i.e., graph contains negativecost cycles)constructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
bellmanFord(Graph, Node, boolean, double[], double[])
,
bellmanFord(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
public static boolean bellmanFord(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
bellmanFord(Graph, Node, boolean, double[], double[], Edge[])
but uses NodeMap
s and DataProvider
s instead of arrays.
Each edge is associated with an arbitrary double value that represents the cost of this edge.
In case the given weighted graph contains no negativecost cycles, this method will yield the shortest
distance from a given node s
to all other nodes. If, on the other hand, the given graph contains
negativecost cycles, this method will yield no reasonable result which will be indicated by the
return value false
.
graph
 the input graphs
 the source nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the double value (cost) for traversing each edgedist
 the NodeMap
that will be filled during the execution and returns a double value (shortest distance)
from node s
to all other nodes or Double.POSITIVE_INFINITY
if no such paths existpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
true
if the algorithm found a valid result,
false
otherwise (i.e., graph contains negativecost cycles)bellmanFord(Graph, Node, boolean, double[], double[])
,
bellmanFord(Graph, Node, boolean, double[], double[], Edge[])
public static boolean singleSource(Graph graph, Node s, boolean directed, double[] cost, double[] dist)
cost.length == graph.E()
dist.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.
true
if the weighted graph does not contain a negativecost cycle, false
otherwisesingleSource(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
,
singleSource(Graph, Node, boolean, double[], double[], Edge[])
public static boolean singleSource(Graph graph, Node s, boolean directed, double[] cost, double[] dist, Edge[] pred)
singleSource(Graph, Node, boolean, double[], double[])
but, additionally, this method
yields the path edges of each calculated shortest path.
pred.length == graph.N()
graph
 the input graphs
 the node from which the shortest path search startsdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest distance from node
s
to all other nodes. The distance from s
to v
is
dist[v.index()]
. If there is no path from s
to v
, then
dist[v.index()] == Double.POSITIVE_INFINITY
.pred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
true
if the weighted graph does not contain a negativecost cycle, false
otherwiseconstructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
singleSource(Graph, Node, boolean, double[], double[])
,
singleSource(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)
public static boolean singleSource(Graph graph, Node s, boolean directed, DataProvider cost, NodeMap dist, NodeMap pred)
singleSource(Graph, Node, boolean, double[], double[], Edge[])
but uses NodeMap
s and
DataProvider
s instead of arrays.
graph
 the input graphs
 the source nodedirected
 true
if the graph should be considered as directed, false
otherwisecost
 the DataProvider
that returns the double value (cost) for traversing each edgedist
 the NodeMap
that will be filled during the execution and returns a double value (shortest distance)
from node s
to all other nodes or Double.POSITIVE_INFINITY
if no such paths existpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
true
if the weighted graph does not contain a negativecost cycle, false
otherwiseconstructNodePath(Node, Node, Edge[])
,
constructEdgePath(Node, Node, Edge[])
,
singleSource(Graph, Node, boolean, double[], double[])
,
singleSource(Graph, Node, boolean, double[], double[], Edge[])
public static boolean allPairs(Graph graph, boolean directed, double[] cost, double[][] dist)
If the given graph contains a negativecost cycle, then false
is returned and the values returned
in dist
are left unspecified.
cost.length == graph.E()
dist
: [graph.N()] [graph.N()]]
O(graph.N()) * O(singleSource)
graph
 the input graphdirected
 true
if the graph should be considered as directed, false
otherwisecost
 an array of double values that returns the costs for traversing each edge; edge e
has cost cost[e.index()]
dist
 an array of values that will be filled during the execution and returns the shortest path distances
from all pairs of nodes s
and t
in the graph. The distance from s
to t
is dist[s.index()][t.index()]
. If there is no path from
s
to t
, then dist[s.index()][t.index()] == Double.POSITIVE_INFINITY
.
true
if the given graph does not contain a negativecost cycle, false
otherwisepublic static void findShortestUniformPaths(Graph graph, Node start, Node end, boolean directed, EdgeMap pathMap)
start
node to target
node.
This method assumes that each edge of the input graph has a cost of 1.0.
O(graph.N() + graph.E())
graph
 the input graphstart
 the start nodeend
 the target nodedirected
 true
if the graph should be considered as directed, false
otherwisepathMap
 the EdgeMap
that will be filled during the execution and returns a boolean value indicating
whether or not the edge belongs to a shortest path connecting the two nodespublic static YList kShortestPaths(Graph graph, DataProvider costDP, Node start, Node end, int k)
k
shortest paths connecting a pair of nodes in a directed graph with
nonnegative edge costs.
The result will be returned as a list of EdgeList
objects.
The cost should be nonnegative.
O(graph.E() + graph.N() * log(graph.N()) + k)
graph
 the input graphcostDP
 the DataProvider
that returns a double value (cost) for traversing each edgestart
 the given start nodeend
 the given target nodek
 a nonnegative integer value
list
of EdgeList
objects each of which represents a path from
start
node to target
node. The i
th path in the
list contains the i
th shortest path between the start
and target
node.public static YCursor kShortestPathsCursor(Graph graph, DataProvider costDP, Node start, Node end, int k)
kShortestPaths(Graph, DataProvider, Node, Node, int)
that returns the result as a special cursor that calculates
the next path in the sequence only when needed.
The returned cursor only supports the operation YCursor.ok()
, YCursor.current()
and
YCursor.next()
.
The cost should be nonnegative.
O(graph.E() + graph.N() * log(graph.N()) + k)
graph
 the input graphcostDP
 the DataProvider
that returns a double value (cost) for traversing each edgestart
 the given start nodeend
 the given target nodek
 a nonnegative integer value
cursor
that calculates the next path in the sequence only when neededpublic static double[] uniformCost(Graph graph)
1.0
for each edge of the
given graph.
graph
 the input graph
1.0
(i.e., for each edge
e: cost[e.index()] == 1.0
)public static NodeList constructNodePath(Node s, Node t, Edge[] pred)
path of nodes
from the
result returned by one of the shortest paths methods defined in this class.
If there is no path from node s
to t
, then an empty list is returned.
s
 the start node of the shortest path which must be the same start node that was
specified when pred
was calculatedt
 the target node of the pathpred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
list
containing the nodes on the shortest path from s
to
t
in the correct orderconstructNodePath(Node, Node, DataProvider)
public static NodeList constructNodePath(Node s, Node t, DataProvider pred)
constructNodePath(Node, Node, Edge[])
but the path edges are given by a DataProvider
.
If there is no path from node s
to t
, then an empty list is returned.
s
 the start node of the shortest path which must be the same start node that was
specified when pred
was calculatedt
 the target node of the pathpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
list
containing the nodes on the shortest path from s
to
t
in the correct orderconstructNodePath(Node, Node, Edge[])
public static EdgeList constructEdgePath(Node s, Node t, Edge[] pred)
path of edges
from the
result returned by one of the shortest paths methods defined in this class.
If there is no path from node s
to t
, then an empty list is returned.
s
 the start node of the shortest path which must be the same start node that was
specified when pred
was calculatedt
 the target node of the pathpred
 an array of Edge
s that will be filled during the execution and returns for each node t
the shortest path edge pred[t.index()]
which is the last edge on the shortest path from
s
to t
. If t == s
or if there is no shortest path from
s
to t
, then pred[t.index()] == null
.
list
containing the edges on the shortest path from s
to
t
in the correct orderconstructEdgePath(Node, Node, DataProvider)
public static EdgeList constructEdgePath(Node s, Node t, DataProvider pred)
constructEdgePath(Node, Node, Edge[])
but the path edges are given by a DataProvider
.
If there is no path from node s
to t
, then an empty list is returned.
s
 the start node of the shortest path which must be the same start node that was
specified when pred
was calculatedt
 the target node of the pathpred
 the NodeMap
that will be filled during the execution and returns for each node t
the
last edge on the shortest path from s
to t
or null
if
t == s
or no shortest path from s
to t
exists
list
containing the edges on the shortest path from s
to
t
in the correct orderconstructEdgePath(Node, Node, Edge[])
public static void findShortestUniformPaths(Graph graph, Node start, DataProvider targetMap, boolean directed, int maxLength, EdgeList pathEdges, NodeList pathNodes)
start
node to a set of target nodes
in the graph not farther away than a given distance.
This method assumes that each edge of the input graph has a cost of 1.0.
maxLength
will not be considered.O(graph.N() + graph.E())
graph
 the input graphstart
 the start nodetargetMap
 the DataProvider
that returns a boolean value indicating whether or not a node belongs to
the set of target nodesdirected
 true
if the graph should be considered as directed, false
otherwisemaxLength
 the maximum edge length of the shortest pathspathEdges
 a list
that will be filled during the execution and returns the edges on the
shortest path from s
to t
in the correct orderpathNodes
 a list
that will be filled during the execution and returns the nodes on the
shortest path from s
to t
in the correct orderpublic static final EdgeList[] shortestPair(Graph graph, Node source, Node target, boolean directed, DataProvider costDP)
s
and t
and have minimum total length.
graph
 the input graphsource
 the source node of the shortest pairtarget
 the target node of the shortest pairdirected
 true
if the graph should be considered as directed, false
otherwisecostDP
 the DataProvider
that returns a double value (cost) for traversing each edge
EdgeList
s holding the resulting edgedisjoint paths
or null
if no such edgedisjoint paths exist

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 