Search this API

## y.algo Class ShortestPaths

```java.lang.Object
y.algo.ShortestPaths
```

`public class ShortestPathsextends java.lang.Object`

This class provides diverse algorithms and helper methods for solving the shortest path problem on weighted graphs.

### Definitions

Given a weighted directed/undirected graph:

• The shortest path problem is the problem of finding a shortest path between a source node `s` and a target node `t` such that the sum of the edge costs is minimized.
• The k-shortest path problem is the problem of finding `k` shortest paths between a source node `s` and a target node `t` such that the sum of the edge costs is minimized.
• The single-source shortest path problem is the problem of finding shortest paths from a source node `s` to all other nodes such that the sum of the edge costs is minimized.
• The single-source single-sink shortest path problem is the problem of finding shortest paths from a source node `s` to a target node `t` such that the sum of the edge costs is minimized.
• The all-pairs shortest path problem is the problem of finding shortest paths between every pair of nodes 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 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 EdgeList` ```aStar(Graph graph, Node s, Node t, boolean directed, DataProvider cost, DataProvider heuristicCost)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).
`static double` ```aStar(Graph graph, Node s, Node t, boolean directed, DataProvider cost, DataProvider heuristicCost, NodeMap pred)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).
`static EdgeList` ```aStar(Graph graph, Node s, Node t, boolean directed, double[] cost, double[] heuristicCost)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).
`static double` ```aStar(Graph graph, Node s, Node t, boolean directed, double[] cost, double[] heuristicCost, Edge[] pred)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star 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 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[])` 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 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 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 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 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 edge-disjoint paths in a non-negatively 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 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 `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 single-source single-sink shortest path problem for arbitrary graphs.
`static void` ```uniform(Graph graph, Node s, boolean directed, double[] dist)```
Solves the single-source 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

### uniform

```public static void uniform(Graph graph,
Node s,
boolean directed,
double[] dist)```
Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of `1.0`.

This method yields the shortest distance from a given node `s` to all other nodes.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Precondition:
`dist.length == graph.N()`
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`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`.

### uniform

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

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Precondition:
`pred.length == graph.N()`
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`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`.
`uniform(Graph, Node, boolean, double[])`, `constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`

### uniform

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

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Precondition:
`pred.length == graph.N()`
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`dist` - 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 exist
`pred` - 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
`uniform(Graph, Node, boolean, double[])`, `constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`

### acyclic

```public static boolean acyclic(Graph graph,
Node s,
double[] cost,
double[] dist)```
Solves the single-source shortest path problem for acyclic directed graphs.

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.

Preconditions:
The graph must be `acyclic`.
`cost.length == graph.E()`
`dist.length == graph.N()`
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`cost` - 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`.
Returns:
`true` if the input graph is acyclic, `false` otherwise
`acyclic(Graph, Node, double[], double[], Edge[])`, `acyclic(Graph, Node, DataProvider, NodeMap, NodeMap)`

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

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.

Precondition:
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`cost` - 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`.
Returns:
`true` if the input graph is acyclic, `false` otherwise
`acyclic(Graph, Node, double[], double[])`, `acyclic(Graph, Node, double[], double[], Edge[])`, `constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`

### acyclic

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

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.

Precondition:
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
`dist` - 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 exist
`pred` - 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
Returns:
`true` if the input graph is acyclic, `false` otherwise
`acyclic(Graph, Node, double[], double[])`, `acyclic(Graph, Node, double[], double[], Edge[])`

### aStar

```public static EdgeList aStar(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost,
double[] heuristicCost)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

Each edge is associated with a non-negative double value that represents the cost of the edge. The costs should be non-negative.

Furthermore, the algorithm uses so-called 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:

• If the heuristic is 'good', i.e., heuristic costs are close to the actual costs, then the algorithm is able to avoid unprofitable search paths and move faster towards the target. Using a good heuristic, this algorithm outperforms other shortest-path algorithms.
• The heuristic must be admissible, which means that it must never overestimate the actual cost to reach the target node. Otherwise, it is not guaranteed that the algorithm actually finds the shortest path. Use `dijkstra(Graph, Node, Node, boolean, double[], Edge[])` if you have no proper problem-specific heuristic.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Preconditions:
`cost.length == graph.E()`
`heuristicCost.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`
Returns:
the list of edges constituting the shortest path from the source node `s` to the sink node `t` or an empty list if there is no such path
`aStar(Graph, Node, Node, boolean, DataProvider, DataProvider)`, `aStar(Graph, Node, Node, boolean, double[], double[], Edge[])`, `aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)`

### aStar

```public static EdgeList aStar(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost,
DataProvider heuristicCost)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

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 non-negative double value that represents the cost of the edge. The costs should be non-negative.

Furthermore, the algorithm uses so-called 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:

• If the heuristic is 'good', i.e., heuristic costs are close to the actual costs, then the algorithm is able to avoid unprofitable search paths and move faster towards the target. Using a good heuristic, this algorithm outperforms other shortest-path algorithms.
• The heuristic must be admissible, which means that it must never overestimate the actual cost to reach the target node. Otherwise, it is not guaranteed that the algorithm actually finds the shortest path. Use `dijkstra(Graph, Node, boolean, double[], double[], Edge[])` if you have no proper problem-specific heuristic.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the cost for traversing an edge
`heuristicCost` - the `DataProvider` that yields for each node the heuristic cost estimate to reach the sink node `t` starting from the node
Returns:
the list of edges constituting the shortest path from the source node `s` to the sink node `t` or an empty list if there is no such path
`aStar(Graph, Node, Node, boolean, double[], double[])`, `aStar(Graph, Node, Node, boolean, double[], double[], Edge[])`, `aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)`

### aStar

```public static double aStar(Graph graph,
Node s,
Node t,
boolean directed,
double[] cost,
double[] heuristicCost,
Edge[] pred)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

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 non-negative double value that represents the cost of the edge. The costs should be non-negative.

Furthermore, the algorithm uses so-called 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:

• If the heuristic is 'good', i.e., heuristic costs are close to the actual costs, then the algorithm is able to avoid unprofitable search paths and move faster towards the target. Using a good heuristic, this algorithm outperforms other shortest-path algorithms.
• The heuristic must be admissible, which means that it must never overestimate the actual cost to reach the target node. Otherwise, it is not guaranteed that the algorithm actually finds the shortest path. Use `dijkstra(Graph, Node, boolean, double[], double[], Edge[])` if you have no proper problem-specific heuristic.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Preconditions:
`cost.length == graph.E()`
`heuristicCost.length == graph.N()`
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
the shortest distance (cost) between `s` and `t` if a path between these two nodes exists or `Double.POSITIVE_INFINITY` otherwise
`aStar(Graph, Node, Node, boolean, double[], double[])`, `aStar(Graph, Node, Node, boolean, DataProvider, DataProvider)`, `aStar(Graph, Node, Node, boolean, DataProvider, DataProvider, NodeMap)`

### aStar

```public static double aStar(Graph graph,
Node s,
Node t,
boolean directed,
DataProvider cost,
DataProvider heuristicCost,
NodeMap pred)```
Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

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 non-negative double value that represents the cost of the edge. The costs should be non-negative.

Furthermore, the algorithm uses so-called 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:

• If the heuristic is 'good', i.e., heuristic costs are close to the actual costs, then the algorithm is able to avoid unprofitable search paths and move faster towards the target. Using a good heuristic, this algorithm outperforms other shortest-path algorithms.
• The heuristic must be admissible, which means that it must never overestimate the actual cost to reach the target node. Otherwise, it is not guaranteed that the algorithm actually finds the shortest path. Use `dijkstra(Graph, Node, boolean, double[], double[], Edge[])` if you have no proper problem-specific heuristic.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the cost for traversing an edge
`heuristicCost` - the `DataProvider` that yields for each node the heuristic cost estimate to reach the sink node `t` starting from the node
`pred` - 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
Returns:
the shortest distance (cost) between `s` and `t` if a path between these two nodes exists or `Double.POSITIVE_INFINITY` otherwise
`aStar(Graph, Node, Node, boolean, double[], double[])`, `aStar(Graph, Node, Node, boolean, DataProvider, DataProvider)`, `aStar(Graph, Node, Node, boolean, double[], double[], Edge[])`

### dijkstra

```public static void dijkstra(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist)```
Solves the single-source shortest path problem for arbitrary graphs.

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Preconditions:
`cost.length == graph.E()`
`dist.length == graph.N()`
Complexity:
`O(graph.E() + graph.N() * log(graph.N())`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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[])`

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

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Precondition:
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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)`

### dijkstra

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

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
`dist` - 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 exist
`pred` - 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
`constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`, `dijkstra(Graph, Node, boolean, double[], double[])`, `dijkstra(Graph, Node, boolean, double[], double[], Edge[])`

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

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Preconditions:
`cost.length == graph.E()`
`pred.length == graph.N()`
Complexity:
`O(graph.E() + graph.N() * log(graph.N())`
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
the distance between `s`and `t` if a path between these two nodes exists or `Double.POSITIVE_INFINITY` otherwise
`constructNodePath(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[])`

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

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - an array of double values that returns the costs for traversing each edge; edge `e` has cost `cost[e.index()]`
Returns:
a shortest `path of edges` between source and sink
`singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])`, `singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider)`, `singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)`

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

Each edge is associated with a non-negative 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 non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
Returns:
a shortest `path of edges` between source and sink
`singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])`, `singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider, NodeMap)`, `singleSourceSingleSink(Graph, Node, Node, boolean, double[])`

### 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 `NodeMap`s and `DataProvider`s instead of arrays.

Each edge is associated with a non-negative double value that represents the cost of the edge.

The costs should be non-negative.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`s` - the source node
`t` - the sink node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
`pred` - 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
Returns:
the distance between `s`and `t` if a path between these two nodes exists or `Double.POSITIVE_INFINITY` otherwise
`singleSourceSingleSink(Graph, Node, Node, boolean, double[], Edge[])`, `singleSourceSingleSink(Graph, Node, Node, boolean, DataProvider)`, `singleSourceSingleSink(Graph, Node, Node, boolean, double[])`

### bellmanFord

```public static boolean bellmanFord(Graph graph,
Node s,
boolean directed,
double[] cost,
double[] dist)```
Solves the single-source shortest path problem for arbitrary graphs.

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 negative-cost cycles, this method will yield no reasonable result which will be indicated by the return value `false`.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

If the graph is considered undirected, each edge with negative costs induces a negative-cost cycle and, thus, the algorithm doesn't return a valid result. Hence, for undirected graphs, all costs must not be negative.
Preconditions:
`cost.length == graph.E()`
`dist.length == graph.N()`
Complexity:
`O(graph.E() * min(D, graph.N()))`, where `D` is the maximum number of edges in any shortest path
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
`true` if the algorithm found a valid result, `false` otherwise (i.e., graph contains negative-cost cycles)
`bellmanFord(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)`, `bellmanFord(Graph, Node, boolean, double[], double[], Edge[])`

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

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 negative-cost cycles, this method will yield no reasonable result which will be indicated by the return value `false`.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

If the graph is considered undirected, each edge with negative costs induces a negative-cost cycle and, thus, the algorithm doesn't return a valid result. Hence, for undirected graphs, all costs must not be negative.
Precondition:
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
`true` if the algorithm found a valid result, `false` otherwise (i.e., graph contains negative-cost cycles)
`constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`, `bellmanFord(Graph, Node, boolean, double[], double[])`, `bellmanFord(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)`

### 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 `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 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`.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

If the graph is considered undirected, each edge with negative costs induces a negative-cost cycle and, thus, the algorithm doesn't return a valid result. Hence, for undirected graphs, all costs must not be negative.
Parameters:
`graph` - the input graph
`s` - the source node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
`dist` - 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 exist
`pred` - 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
Returns:
`true` if the algorithm found a valid result, `false` otherwise (i.e., graph contains negative-cost cycles)
`bellmanFord(Graph, Node, boolean, double[], double[])`, `bellmanFord(Graph, Node, boolean, double[], double[], Edge[])`

### 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 work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.
Preconditions:
`cost.length == graph.E()`
`dist.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
`true` if the weighted graph does not contain a negative-cost cycle, `false` otherwise
`singleSource(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)`, `singleSource(Graph, Node, boolean, double[], double[], Edge[])`

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

Depending on the structure of the given graph and the values of the given edge costs it delegates its work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.
Precondition:
`pred.length == graph.N()`
Parameters:
`graph` - the input graph
`s` - the node from which the shortest path search starts
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
`true` if the weighted graph does not contain a negative-cost cycle, `false` otherwise
`constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`, `singleSource(Graph, Node, boolean, double[], double[])`, `singleSource(Graph, Node, boolean, DataProvider, NodeMap, NodeMap)`

### 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 `NodeMap`s and `DataProvider`s instead of arrays.

Depending on the structure of the given graph and the values of the given edge costs it delegates its work to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.
Parameters:
`graph` - the input graph
`s` - the source node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - the `DataProvider` that returns the double value (cost) for traversing each edge
`dist` - 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 exist
`pred` - 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
Returns:
`true` if the weighted graph does not contain a negative-cost cycle, `false` otherwise
`constructNodePath(Node, Node, Edge[])`, `constructEdgePath(Node, Node, Edge[])`, `singleSource(Graph, Node, boolean, double[], double[])`, `singleSource(Graph, Node, boolean, double[], double[], Edge[])`

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

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Preconditions:
`cost.length == graph.E()`
Dimension of `dist`: `[graph.N()] [graph.N()]]`
Complexity:
`O(graph.N()) * O(singleSource)`
Parameters:
`graph` - the input graph
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`cost` - 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`.
Returns:
`true` if the given graph does not contain a negative-cost cycle, `false` otherwise

### 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` node to `target` node.

This method assumes that each edge of the input graph has a cost of 1.0.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`start` - the start node
`end` - the target node
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`pathMap` - 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 nodes

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

The cost should be non-negative.

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.
Complexity:
`O(graph.E() + graph.N() * log(graph.N()) + k)`
Parameters:
`graph` - the input graph
`costDP` - the `DataProvider` that returns a double value (cost) for traversing each edge
`start` - the given start node
`end` - the given target node
`k` - a non-negative integer value
Returns:
a `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.

### 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 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 non-negative.

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.
Complexity:
`O(graph.E() + graph.N() * log(graph.N()) + k)`
Parameters:
`graph` - the input graph
`costDP` - the `DataProvider` that returns a double value (cost) for traversing each edge
`start` - the given start node
`end` - the given target node
`k` - a non-negative integer value
Returns:
a `cursor` that calculates the next path in the sequence only when needed

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

Parameters:
`graph` - the input graph
Returns:
an array that contains uniform edge costs of value `1.0` (i.e., 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 `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.

Parameters:
`s` - the start node of the shortest path which must be the same start node that was specified when `pred` was calculated
`t` - the target node of the path
`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`.
Returns:
a `list` containing the nodes on the shortest path from `s` to `t` in the correct order
`constructNodePath(Node, Node, DataProvider)`

### constructNodePath

```public static NodeList constructNodePath(Node s,
Node t,
DataProvider pred)```
Like `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.

Parameters:
`s` - the start node of the shortest path which must be the same start node that was specified when `pred` was calculated
`t` - the target node of the path
`pred` - 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
Returns:
a `list` containing the nodes on the shortest path from `s` to `t` in the correct order
`constructNodePath(Node, Node, Edge[])`

### constructEdgePath

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

If there is no path from node `s` to `t`, then an empty list is returned.

Parameters:
`s` - the start node of the shortest path which must be the same start node that was specified when `pred` was calculated
`t` - the target node of the path
`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`.
Returns:
a `list` containing the edges on the shortest path from `s` to `t` in the correct order
`constructEdgePath(Node, Node, DataProvider)`

### constructEdgePath

```public static EdgeList constructEdgePath(Node s,
Node t,
DataProvider pred)```
Like `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.

Parameters:
`s` - the start node of the shortest path which must be the same start node that was specified when `pred` was calculated
`t` - the target node of the path
`pred` - 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
Returns:
a `list` containing the edges on the shortest path from `s` to `t` in the correct order
`constructEdgePath(Node, Node, Edge[])`

### 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 a `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.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.

Shortest paths longer than `maxLength` will not be considered.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`start` - the start node
`targetMap` - the `DataProvider` that returns a boolean value indicating whether or not a node belongs to the set of target nodes
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`maxLength` - the maximum edge length of the shortest paths
`pathEdges` - a `list` that will be filled during the execution and returns the edges on the shortest path from `s` to `t` in the correct order
`pathNodes` - a `list` that will be filled during the execution and returns the nodes on the shortest path from `s` to `t` in the correct order

### shortestPair

```public static final EdgeList[] shortestPair(Graph graph,
Node source,
Node target,
boolean directed,
DataProvider costDP)```
Returns two edge-disjoint paths in a non-negatively weighted directed graph, such that both paths connect nodes `s` and `t` and have minimum total length.

If the graph is considered undirected, each edge can be traversed in both directions and the returned shortest paths can, thus, be undirected.
Parameters:
`graph` - the input graph
`source` - the source node of the shortest pair
`target` - the target node of the shortest pair
`directed` - `true` if the graph should be considered as directed, `false` otherwise
`costDP` - the `DataProvider` that returns a double value (cost) for traversing each edge
Returns:
a two-dimensional array of `EdgeList`s holding the resulting edge-disjoint paths or `null` if no such edge-disjoint paths exist