y.algo
Class ShortestPaths

java.lang.Object
  y.algo.ShortestPaths

public class ShortestPaths
extends Object

Provides diverse algorithms and helper methods for solving the shortest path problem on weighted graphs.

Method Summary

static boolean	acyclic(Graph graph, Node s, DataProvider cost, NodeMap dist, NodeMap pred) Like acyclic(Graph, Node, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static boolean	acyclic(Graph graph, Node s, double[] cost, double[] dist) This method solves the single-source 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 all-pairs shortest path problem for graphs with arbitrary edge costs.
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 NodeMaps and DataProviders instead of arrays.
static boolean	bellmanFord(Graph graph, Node s, boolean directed, double[] cost, double[] dist) This method solves the single-source 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[]) with the difference that the path edges are given by a DataProvider.
static EdgeList	constructEdgePath(Node s, Node t, Edge[] pred) Convenience method that constructs an explicit edge path from the result yielded 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[]) with the difference that the path edges are given by a DataProvider.
static NodeList	constructNodePath(Node s, Node t, Edge[] pred) Convenience method that constructs an explicit node path from the result yielded 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[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.
static void	dijkstra(Graph graph, Node s, boolean directed, double[] cost, double[] dist) This method solves the single-source 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 start 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 to end 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 non-negative 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 its result not as a list but 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 edge-disjoint paths from in a nonnegatively-weighted directed graph, so that both paths connect 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 NodeMaps and DataProviders instead of arrays.
static boolean	singleSource(Graph graph, Node s, boolean directed, double[] cost, double[] dist) This method solves the single-source 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 NodeMaps and DataProviders 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 single-source single-sink shortest path problem for arbitrary graphs.
static void	uniform(Graph graph, Node s, boolean directed, double[] dist) This method solves the single-source shortest path problem for arbitrary graphs where 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 this method yields the path 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[], Edge[]) but uses NodeMaps 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

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           double[] dist)

This method solves the single-source shortest path problem for arbitrary graphs where each edge has a uniform cost of 1.0. This method yields the shortest distance from a given node s to all other nodes.

Parameters:

graph - the graph being acted upon

s - the start node for the shortest path search

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

dist - return value that will hold 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.

Complexity:

O(graph.N()+graph.E())

Precondition:

dist.length == graph.N()

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           double[] dist,
                           Edge[] pred)

Like uniform(Graph, Node, boolean, double[]) but additionally this method yields the path edges of each calculated shortest path.

Parameters:

pred - return value that 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Precondition:

pred.length == graph.N()

uniform

public static void uniform(Graph graph,
                           Node s,
                           boolean directed,
                           NodeMap dist,
                           NodeMap pred)

Like uniform(Graph, Node, boolean, double[], Edge[]) but uses NodeMaps instead of arrays.

Parameters:

dist - return value. the map will provide a double value for each node.

pred - return value. the map will provide an Edge for each node.

acyclic

public static boolean acyclic(Graph graph,
                              Node s,
                              double[] cost,
                              double[] dist)

This method solves the single-source shortest path problem for acyclic directed graphs. Associated with each edge is 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.

Parameters:

graph - the graph being acted upon

s - the start node for the shortest path search

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

dist - return value that will hold 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.

Returns:

false if the input graph was not acyclic.

Complexity:

O(graph.N()+graph.E())

Preconditions:

GraphChecker.isAcyclic(graph)

cost.length == graph.E()

dist.length == graph.N()

acyclic

public 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.

Parameters:

pred - return value that 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Precondition:

pred.length == graph.N()

acyclic

public static boolean acyclic(Graph graph,
                              Node s,
                              DataProvider cost,
                              NodeMap dist,
                              NodeMap pred)

Like acyclic(Graph, Node, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:

cost - must provide a double value for each edge.

dist - return value. the map will provide a double value for each node.

pred - return value. the map will provide an Edge for each node.

dijkstra

public static void dijkstra(Graph graph,
                            Node s,
                            boolean directed,
                            double[] cost,
                            double[] dist)

This method solves the single-source shortest path problem for arbitrary graphs. Associated with each edge is a non-negative double value that represents the cost of that edge. This method yields the shortest distance from a given node s to all other nodes.

Parameters:

graph - the graph being acted upon

s - the start node for the shortest path search

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

dist - return value that will hold 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.

Complexity:

O(graph.E()+graph.N()*log(graph.N())

Preconditions:

For each edge e: cost[e.index()] >= 0

cost.length == graph.E()

dist.length == graph.N()

dijkstra

public 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.

Parameters:

pred - return value that 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Precondition:

pred.length == graph.N()

dijkstra

public static void dijkstra(Graph graph,
                            Node s,
                            boolean directed,
                            DataProvider cost,
                            NodeMap dist,
                            NodeMap pred)

Like dijkstra(Graph, Node, boolean, double[], double[], Edge[]) but uses NodeMaps and DataProviders instead of arrays.

Parameters:

cost - must provide a double value for each edge.

dist - return value. the map will provide a double value for each node.

pred - return value. the map will provide an Edge for each node.

singleSourceSingleSink

public static double singleSourceSingleSink(Graph graph,
                                            Node s,
                                            Node t,
                                            boolean directed,
                                            double[] cost,
                                            Edge[] pred)

This method solves the single-source single-sink shortest path problem for arbitrary graphs. Associated with each edge is a non-negative double value that represents the cost of that edge. This method returns the shortest distance from node s to node t. It also returns information to construct the actual path between these to nodes.

Parameters:

graph - the graph being acted upon

s - the source node for the shortest path search

t - the sink node for the shortest path search

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

pred - return value that holds for each node v on the the shortest the path from s to t an edge pred[v.index()] which is the last edge on the shortest path from s to v. If v == s or if there is no shortest path from s to v then pred[v.index()] == null.

Returns:

the distance between s and t if a path between these two nodes exist and Double.POSITIVE_INFINITY otherwise.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Complexity:

O(graph.E()+graph.N()*log(graph.N())

Preconditions:

For each edge e: cost[e.index()] >= 0

cost.length == graph.E()

pred.length == graph.N()

singleSourceSingleSink

public 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. If the returned path is empty then there is no path between the nodes.

Returns:

a shortest path between source and sink

singleSourceSingleSink

public 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. If the returned path is empty then there is no path between the nodes.

Returns:

a shortest path between source and sink

singleSourceSingleSink

public 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 NodeMaps and DataProviders instead of arrays.

Parameters:

cost - must provide a double value for each edge.

pred - return value. the map will provide an Edge for each node.

bellmanFord

public static boolean bellmanFord(Graph graph,
                                  Node s,
                                  boolean directed,
                                  double[] cost,
                                  double[] dist)

This method solves the single-source shortest path problem for arbitrary graphs. Associated with each edge is an arbitrary double value that represents the cost of that 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 negative-cost cycles this method will yield no reasonable result which will be indicated by the return value false.

Parameters:

graph - the graph being acted upon

s - the start node for the shortest path search

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

dist - return value that will hold 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.

Returns:

false if this weighted graph contains a negative cost cycle, true otherwise.

Complexity:

O(graph.E()*min(D,graph.N())) where D is the maximal number of edges in any shortest path.

Preconditions:

cost.length == graph.E()

dist.length == graph.N()

bellmanFord

public 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.

Parameters:

pred - return value that 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Precondition:

pred.length == graph.N()

bellmanFord

public 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 NodeMaps and DataProviders instead of arrays.

Parameters:

cost - must provide a double value for each edge.

dist - return value. the map will provide a double value for each node.

pred - return value. the map will provide an Edge for each node.

singleSource

public static boolean singleSource(Graph graph,
                                   Node s,
                                   boolean directed,
                                   double[] cost,
                                   double[] dist)

This method solves the single-source shortest path problem for arbitrary graphs. Depending on the structure of the given graph and the values of the given edge costs it delegates its job to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.

Parameters:

graph - the graph being acted upon

s - the start node for the shortest path search

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

dist - return value that will hold 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.

Returns:

false if this weighted graph contains a negative cost cycle, true otherwise.

Preconditions:

cost.length == graph.E()

dist.length == graph.N()

singleSource

public 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.

Parameters:

pred - return value that 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.

See Also:

constructNodePath(Node, Node, Edge[]), constructEdgePath(Node, Node, Edge[])

Precondition:

pred.length == graph.N()

singleSource

public 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 NodeMaps and DataProviders instead of arrays.

Parameters:

cost - must provide a double value for each edge.

dist - return value. the map will provide a double value for each node.

pred - return value. the map will provide an Edge for each node.

allPairs

public static boolean allPairs(Graph graph,
                               boolean directed,
                               double[] cost,
                               double[][] dist)

This method solves the all-pairs shortest path problem for graphs with arbitrary edge costs. If the given graph contains a negative cost cycle, then false is returned and the values returned in dist are left unspecified.

Parameters:

graph - the graph being acted upon

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

cost - holds the costs for traversing each edge. Edge e has cost cost[e.index()].

dist - return value that will hold 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.

Returns:

whether or not the given graph contains a negative cost cycle.

Complexity:

O(graph.N())*O(singleSource)

Preconditions:

cost.length == graph.E();

dimension of dist: [graph.N()][graph.N()]]

findShortestUniformPaths

public static void findShortestUniformPaths(Graph graph,
                                            Node start,
                                            Node end,
                                            boolean directed,
                                            EdgeMap pathMap)

Marks all edges that belong to a shortest path from start to end node. This method assumes that each edge of the input graph has a cost of 1.0.

Parameters:

graph - the input graph

start - the start node

end - the end node

directed - whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.

pathMap - the result. For each edge a boolean value will indicate whether or not it belongs to a shortest path connecting the two nodes.

Complexity:

O(g.N()+g.E())

kShortestPaths

public 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 non-negative edge costs. The result will be returned as a list of EdgeList objects. Note that the returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.

Parameters:

graph - the graph being acted upon

costDP - a data provider that provides a double-valued cost for each edge of the input graph.

start - start node of the shortest paths

end - the end node of the shortest paths

k -

Returns:

a list of EdgeList objects each of which representing a path from start to end node. The i-th path in the list contains the i-th shortest path between start and end node. Note that the returned list may contain less than k paths in case there are fewer directed paths between start and end node.

Complexity:

O(graph.E() + graph.N()*log(graph.N()) + k)

Precondition:

For each edge e: costDP.getDouble(e) >= 0

kShortestPathsCursor

public static YCursor kShortestPathsCursor(Graph graph,
                                           DataProvider costDP,
                                           Node start,
                                           Node end,
                                           int k)

A variant of kShortestPaths(Graph, DataProvider, Node, Node, int) that returns its result not as a list but 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().

uniformCost

public 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.

Returns:

an array cost[] that contains uniform edge costs of 1.0 for each edge e: cost[e.index()] == 1.0.

constructNodePath

public static NodeList constructNodePath(Node s,
                                         Node t,
                                         Edge[] pred)

Convenience method that constructs an explicit node path from the result yielded by one of the shortest paths methods defined in this class.

Parameters:

s - the start node of the shortest path. This must be the same start node that was specified when pred was calculated.

t - the end node of the path

pred - the shortest path edge result array returned by one of the shortest path edge methods defined in this class.

Returns:

a node list that holds the nodes on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.

constructNodePath

public static NodeList constructNodePath(Node s,
                                         Node t,
                                         DataProvider pred)

Like constructNodePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.

Parameters:

pred - the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.

constructEdgePath

public static EdgeList constructEdgePath(Node s,
                                         Node t,
                                         Edge[] pred)

Convenience method that constructs an explicit edge path from the result yielded by one of the shortest paths methods defined in this class.

Parameters:

s - the start node of the shortest path. This must be the same start node that was specified when pred was calculated.

t - the end node of the path

pred - the shortest path edge result array returned by one of the shortest path edge methods defined in this class.

Returns:

an edge list that holds the edges on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.

constructEdgePath

public static EdgeList constructEdgePath(Node s,
                                         Node t,
                                         DataProvider pred)

Like constructEdgePath(Node,Node,Edge[]) with the difference that the path edges are given by a DataProvider.

Parameters:

pred - the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.

findShortestUniformPaths

public 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 start 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.

Parameters:

graph - the input graph

start - the start node

targetMap - a boolean data provider that marks the target nodes. If the data provider is null all nodes in the graph are assumed to be target nodes.

directed - whether or not to work on directed edges

maxLength - the maximum edge length of the shortest paths. Shortest paths that are longer than this value will not be considered.

pathEdges - a return value. If this parameter is not null, this algorithm first clears the list and then adds all edges that belong to the detected shortest paths.

pathNodes - a return value. If this parameter is not null, this algorithm first clears the list and then adds all nodes that belong to the detected shortest paths.

Complexity:

O(g.N()+g.E())

shortestPair

public static final EdgeList[] shortestPair(Graph graph,
                                            Node source,
                                            Node target,
                                            boolean directed,
                                            DataProvider costDP)

Returns two edge-disjoint paths from in a nonnegatively-weighted directed graph, so that both paths connect s and t and have minimum total length.

Parameters:

graph - the graph being acted upon

source - source node of the shortest pair

target - end node of the shortest pair

directed - whether or not to interpret the edges as directed or undirected

costDP - a data provider that provides a double-valued cost for each edge of the input graph.

Returns:

a two-dimensional EdgeList array that holds the resulting edge-disjoint paths, or null if no such edge-disjoint paths exist.