ShortestPathAlgorithm

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

Inheritance Hierarchy

ShortestPathAlgorithm

Remarks

Note: Methods of this class work with instances of Graph. To find shortest paths in an IGraph use one of the following classes instead:

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.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.ShortestPaths

Static Methods

acyclic

(graph: Graph, s: YNode, cost: number[], dist: number[], pred?: Edge[]) : boolean

Solves the single-source shortest path problem for acyclic directed graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the node from which the shortest path search starts
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
dist - number[]: 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 - Edge[]: an array of Edges 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

↪boolean: true if the input graph is acyclic, false otherwise

acyclic

(graph: Graph, s: YNode, cost: IDataProvider, dist: INodeMap, pred: INodeMap) : boolean

Solves the single-source shortest path problem for acyclic directed graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the node from which the shortest path search starts

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

dist - INodeMap

the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Number.POSITIVE_INFINITY if no such paths exist

Domain	YNode
Values	number	a value representing the shortest distance from node `s` to all other nodes or if no such paths exist

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪boolean: true if the input graph is acyclic, false otherwise

allPairs

(graph: Graph, directed: boolean, cost: number[], dist: number[]) : boolean

This method solves the all-pairs shortest path problem for graphs with arbitrary edge costs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths between all pairs of nodes in an IGraph use AllPairsShortestPaths instead.

If the given graph contains a negative-cost cycle, then false is returned and the values returned in dist are left unspecified.

Complexity

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

Preconditions

cost.length == graph.E()
Dimension of dist: [graph.N()] [graph.N()]]

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
dist - number[]: 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

↪boolean: true if the given graph does not contain a negative-cost cycle, false otherwise

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

aStar

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: number[], heuristicCost: number[]) : EdgeList

Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead. Use the heuristic property to use 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 if you have no proper problem-specific heuristic.

Preconditions

cost.length == graph.E()
heuristicCost.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the source node
t - YNode: the sink node
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that represent the costs for traversing each edge; edge e has cost cost[e.index()]
heuristicCost - number[]: 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

↪EdgeList: 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: Graph, s: YNode, t: YNode, directed: boolean, cost: IDataProvider, heuristicCost: IDataProvider) : EdgeList

Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead. Use the heuristic property to use A*.

This method is like aStar, with the only difference that it takes IDataProviders 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.

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 if you have no proper problem-specific heuristic.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

t - YNode

the sink node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the cost for traversing an edge

Domain	Edge
Values	number	a value representing the cost for traversing the edge

heuristicCost - IDataProvider

the IDataProvider that yields for each node the heuristic cost estimate to reach the sink node t starting from the node

Domain	YNode
Values	number	a value that represents an estimate to reach the sink node `t` from the associated node. The heuristic should never overestimate the costs

Returns

↪EdgeList: 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: Graph, s: YNode, t: YNode, directed: boolean, cost: number[], heuristicCost: number[], pred: Edge[]) : number

Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead. Use the heuristic property to use A*.

This method is like aStar, 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 or constructNodePath.

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 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 if you have no proper problem-specific heuristic.

Preconditions

cost.length == graph.E()
heuristicCost.length == graph.N()
pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the source node
t - YNode: the sink node
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that represent the costs for traversing each edge; edge e has cost cost[e.index()]
heuristicCost - number[]: 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 - Edge[]: an array of Edges 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

↪number: the shortest distance (cost) between s and t if a path between these two nodes exists or Number.POSITIVE_INFINITY otherwise

aStar

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: IDataProvider, heuristicCost: IDataProvider, pred: INodeMap) : number

Solves the single-source single-sink shortest path problem for arbitrary graphs using an implementation of the well-known a-star algorithm (A*).

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead. Use the heuristic property to use A*.

This method is like aStar, with the only difference that it takes IDataProviders and a INodeMap 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.

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 if you have no proper problem-specific heuristic.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

t - YNode

the sink node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the cost for traversing an edge

Domain	Edge
Values	number	a value representing the cost for traversing the edge

heuristicCost - IDataProvider

the IDataProvider that yields for each node the heuristic cost estimate to reach the sink node t starting from the node

Domain	YNode
Values	number	a value that represents an estimate to reach the sink node `t` from the associated node. The heuristic should never overestimate the costs.

pred - INodeMap

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

Domain	YNode
Values	Edge	an edge representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪number: the shortest distance (cost) between s and t if a path between these two nodes exists or Number.POSITIVE_INFINITY otherwise

bellmanFord

(graph: Graph, s: YNode, directed: boolean, cost: number[], dist: number[], pred?: Edge[]) : boolean

Solves the single-source shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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.

Preconditions

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the node from which the shortest path search starts
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
dist - number[]: 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 - Edge[]: an array of Edges 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

↪boolean: true if the algorithm found a valid result, false otherwise (i.e., graph contains negative-cost cycles)

bellmanFord

(graph: Graph, s: YNode, directed: boolean, cost: IDataProvider, dist: INodeMap, pred: INodeMap) : boolean

Solves the single-source shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

dist - INodeMap

the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Number.POSITIVE_INFINITY if no such paths exist

Domain	YNode
Values	number	a value representing the shortest distance from node `s` to all other nodes or if no such paths exist

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪boolean: true if the algorithm found a valid result, false otherwise (i.e., graph contains negative-cost cycles)

constructEdgePath

(s: YNode, t: YNode, pred: Edge[]) : EdgeList

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

Remarks

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

Parameters

options - Object
A map of options to pass to the method.

s - YNode: the start node of the shortest path which must be the same start node that was specified when pred was calculated
t - YNode: the target node of the path
pred - Edge[]: an array of Edges 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

↪EdgeList: a list containing the edges on the shortest path from s to t in the correct order

constructEdgePath

(s: YNode, t: YNode, pred: IDataProvider) : EdgeList

Like constructEdgePath but the path edges are given by a IDataProvider.

Remarks

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

Parameters

options - Object
A map of options to pass to the method.

s - YNode

the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - YNode

the target node of the path

pred - IDataProvider

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪EdgeList: a list containing the edges on the shortest path from s to t in the correct order

constructNodePath

(s: YNode, t: YNode, pred: Edge[]) : YNodeList

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

Remarks

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

Parameters

options - Object
A map of options to pass to the method.

s - YNode: the start node of the shortest path which must be the same start node that was specified when pred was calculated
t - YNode: the target node of the path
pred - Edge[]: an array of Edges 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

↪YNodeList: a list containing the nodes on the shortest path from s to t in the correct order

constructNodePath

(s: YNode, t: YNode, pred: IDataProvider) : YNodeList

Like constructNodePath but the path edges are given by a IDataProvider.

Remarks

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

Parameters

options - Object
A map of options to pass to the method.

s - YNode

the start node of the shortest path which must be the same start node that was specified when pred was calculated

t - YNode

the target node of the path

pred - IDataProvider

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪YNodeList: a list containing the nodes on the shortest path from s to t in the correct order

dijkstra

(graph: Graph, s: YNode, directed: boolean, cost: number[], dist: number[], pred?: Edge[])

Solves the single-source shortest path problem for arbitrary graphs and additionally, this method yields the path edges of each calculated shortest path.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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.

Preconditions

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the node from which the shortest path search starts
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
dist - number[]: 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 - Edge[]: an array of Edges 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.

dijkstra

(graph: Graph, s: YNode, directed: boolean, cost: IDataProvider, dist: INodeMap, pred: INodeMap)

Solves the single-source shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

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.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the node from which the shortest path search starts

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

dist - INodeMap

the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Number.POSITIVE_INFINITY if no such paths exist

Domain	YNode
Values	number	a value representing the shortest distance from node `s` to all other nodes or if no such paths exist

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

findShortestUniformPaths

(graph: Graph, start: YNode, end: YNode, directed: boolean, pathMap: IEdgeMap)

Marks all edges that belong to a shortest path from start node to target node.

Remarks

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

Complexity

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

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

start - YNode

the start node

end - YNode

the target node

directed - boolean

true if the graph should be considered as directed, false otherwise

pathMap - IEdgeMap

the IEdgeMap 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

Domain	Edge
Values	boolean	`true` if the edge belongs to a shortest path connecting the two nodes, `false` otherwise

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

findShortestUniformPaths

(graph: Graph, start: YNode, targetMap: IDataProvider, directed: boolean, maxLength: number, pathEdges: EdgeList, pathNodes: YNodeList)

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.

Remarks

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

Complexity

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

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

start - YNode

the start node

targetMap - IDataProvider

the IDataProvider that returns a boolean value indicating whether or not a node belongs to the set of target nodes

Domain	YNode
Values	boolean	`true` if the node belongs to the set of target nodes, `false` otherwise

directed - boolean

true if the graph should be considered as directed, false otherwise

maxLength - number

the maximum edge length of the shortest paths

pathEdges - EdgeList

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 - YNodeList

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

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.

kShortestPaths

(graph: Graph, costDP: IDataProvider, start: YNode, end: YNode, k: number) : YList

This method finds the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.

Remarks

The result will be returned as a list of EdgeList objects.

The cost should be non-negative.

Complexity

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

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

costDP - IDataProvider

the IDataProvider that returns a double value (cost) for traversing each edge

Domain	Edge
Values	number	value representing the cost of each edge

start - YNode

the given start node

end - YNode

the given target node

k - number

a non-negative integer value

Returns

↪YList: 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.

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.

The returned list may contain less than k paths in case there are fewer directed paths between the start and target node.

kShortestPathsCursor

(graph: Graph, costDP: IDataProvider, start: YNode, end: YNode, k: number) : ICursor

A variant of kShortestPaths that returns the result as a special cursor that calculates the next path in the sequence only when needed.

Remarks

The returned cursor only supports the operation ok, current and next.

The cost should be non-negative.

Complexity

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

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

costDP - IDataProvider

the IDataProvider that returns a double value (cost) for traversing each edge

Domain	Edge
Values	number	value representing the cost of each edge

start - YNode

the given start node

end - YNode

the given target node

k - number

a non-negative integer value

Returns

↪ICursor: a cursor that calculates the next path in the sequence only when needed

The returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.

The returned list may contain less than k paths in case there are fewer directed paths between the start and target node.

shortestPair

(graph: Graph, source: YNode, target: YNode, directed: boolean, costDP: IDataProvider) : EdgeList

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.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

source - YNode

the source node of the shortest pair

target - YNode

the target node of the shortest pair

directed - boolean

true if the graph should be considered as directed, false otherwise

costDP - IDataProvider

the IDataProvider that returns a double value (cost) for traversing each edge

Domain	Edge
Values	number	value representing the cost of each edge

Returns

↪EdgeList[]: a two-dimensional array of EdgeLists holding the resulting edge-disjoint paths or null if no such edge-disjoint paths exist

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

singleSource

(graph: Graph, s: YNode, directed: boolean, cost: number[], dist: number[], pred?: Edge[]) : boolean

This method solves the single-source shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

Preconditions

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the node from which the shortest path search starts
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
dist - number[]: 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 - Edge[]: an array of Edges 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

↪boolean: true if the weighted graph does not contain a negative-cost cycle, false otherwise

singleSource

(graph: Graph, s: YNode, directed: boolean, cost: IDataProvider, dist: INodeMap, pred: INodeMap) : boolean

This method solves the single-source shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

dist - INodeMap

the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Number.POSITIVE_INFINITY if no such paths exist

Domain	YNode
Values	number	a value representing the shortest distance from node `s` to all other nodes or if no such paths exist

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪boolean: true if the weighted graph does not contain a negative-cost cycle, false otherwise

singleSourceSingleSink

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: number[], pred: Edge[]) : number

This method solves the single-source single-sink shortest path problem for arbitrary graphs.

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead.

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.

Complexity

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

Preconditions

cost.length == graph.E()
pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the source node
t - YNode: the sink node
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]
pred - Edge[]: an array of Edges 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

↪number: the distance between sand t if a path between these two nodes exists or Number.POSITIVE_INFINITY otherwise

singleSourceSingleSink

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: number[]) : EdgeList

Similar to singleSourceSingleSink but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead.

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.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the source node
t - YNode: the sink node
directed - boolean: true if the graph should be considered as directed, false otherwise
cost - number[]: an array of double values that returns the costs for traversing each edge; edge e has cost cost[e.index()]

Returns

↪EdgeList: a shortest path of edges between source and sink

singleSourceSingleSink

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: IDataProvider) : EdgeList

Similar to singleSourceSingleSink but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned.

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead.

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.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

t - YNode

the sink node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

Returns

↪EdgeList: a shortest path of edges between source and sink

singleSourceSingleSink

(graph: Graph, s: YNode, t: YNode, directed: boolean, cost: IDataProvider, pred: INodeMap) : number

Like singleSourceSingleSink but uses INodeMaps and IDataProviders instead of arrays.

Remarks

Note: This method works with instances of Graph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead.

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

The costs should be non-negative.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the source node

t - YNode

the sink node

directed - boolean

true if the graph should be considered as directed, false otherwise

cost - IDataProvider

the IDataProvider that returns the double value (cost) for traversing each edge

Domain	Edge
Values	number	a value representing the cost of traversing each edge

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

Returns

↪number: the distance between sand t if a path between these two nodes exists or Number.POSITIVE_INFINITY otherwise

uniform

(graph: Graph, s: YNode, directed: boolean, dist: number[], pred?: Edge[])

Solves the single-source shortest path problem for arbitrary graphs in which each edge has a uniform cost of 1.0.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

Complexity

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

Preconditions

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph
s - YNode: the node from which the shortest path search starts
directed - boolean: true if the graph should be considered as directed, false otherwise
dist - number[]: 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 - Edge[]: an array of Edges 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: Graph, s: YNode, directed: boolean, dist: INodeMap, pred: INodeMap)

Like uniform but uses INodeMaps instead of arrays.

Remarks

Note: This method works with instances of Graph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.

Complexity

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

Preconditions

pred.length == graph.N()

Parameters

options - Object
A map of options to pass to the method.

graph - Graph

the input graph

s - YNode

the node from which the shortest path search starts

directed - boolean

true if the graph should be considered as directed, false otherwise

dist - INodeMap

the INodeMap that will be filled during the execution and returns a double value (shortest distance) from node s to all other nodes or Number.POSITIVE_INFINITY if no such paths exist

Domain	YNode
Values	number	a value representing the shortest distance from node `s` to all other nodes or if no such paths exist

pred - INodeMap

the INodeMap 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

Domain	YNode
Values	Edge	an representing for each node `t` the last edge on the shortest path from `s` to node `t` or `null` if `t == s` or no shortest path from `s` to `t` exists

uniformCost

(graph: Graph) : number

Convenience method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the input graph

Returns

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

ShortestPathAlgorithm

Remarks

Definitions

Type Details

Static Methods

acyclic

Remarks

Preconditions

Parameters

Returns

See Also

acyclic

Remarks

Preconditions

Parameters

Returns

See Also

allPairs

Remarks

Complexity

Preconditions

Parameters

Returns

aStar

Remarks

Preconditions

Parameters

Returns

See Also

aStar

Remarks

Parameters

Returns

See Also

aStar

Remarks

Preconditions

Parameters

Returns

See Also

aStar

Remarks

Parameters

Returns

See Also

bellmanFord

Remarks

Preconditions

Parameters

Returns

See Also

bellmanFord

Remarks

Parameters

Returns

See Also

constructEdgePath

Remarks

Parameters

Returns

See Also

constructEdgePath

Remarks

Parameters

Returns

See Also

constructNodePath

Remarks

Parameters

Returns

See Also

constructNodePath

Remarks

Parameters

Returns

See Also

dijkstra

Remarks

Preconditions

Parameters