| Package | com.yworks.yfiles.algo |
| Class | public class ShortestPaths |
| Inheritance | ShortestPaths  YObject Object |
| Method | Defined By | ||
|---|---|---|---|
ShortestPaths(init:Boolean = true) | ShortestPaths | ||
[static]
This method solves the single-source shortest path problem for acyclic directed graphs. | ShortestPaths | ||
[static]
Like acyclicWithPaths() but uses NodeMaps and DataProviders instead of arrays. | ShortestPaths | ||
acyclicWithPaths(graph:Graph, s:Node, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):Boolean [static]
Like acyclic() but additionally this method yields the path edges of each calculated shortest path. | ShortestPaths | ||
[static]
This method solves the all-pairs shortest path problem for graphs with arbitrary edge costs. | ShortestPaths | ||
bellmanFord(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>):Boolean [static]
This method solves the single-source shortest path problem for arbitrary graphs. | ShortestPaths | ||
bellmanFordWithPath(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):Boolean [static]
Like bellmanFord() but additionally this method yields the path edges of each calculated shortest path. | ShortestPaths | ||
bellmanFordWithPath2(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):Boolean [static]
Like bellmanFordWithPath() but uses NodeMaps and DataProviders instead of arrays. | ShortestPaths | ||
[static]
Convenience method that constructs an explicit edge path from the result yielded by one of the shortest paths methods defined in this class. | ShortestPaths | ||
[static]
Like constructEdgePath() with the difference that the path edges are given by a DataProvider. | ShortestPaths | ||
[static]
Convenience method that constructs an explicit node path from the result yielded by one of the shortest paths methods defined in this class. | ShortestPaths | ||
[static]
Like constructNodePath() with the difference that the path edges are given by a DataProvider. | ShortestPaths | ||
[static]
This method solves the single-source shortest path problem for arbitrary graphs. | ShortestPaths | ||
dijkstra2(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):void [static]
Like dijkstraGetPaths() but uses NodeMaps and DataProviders instead of arrays. | ShortestPaths | ||
dijkstraGetPaths(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):void [static]
Like dijkstra() but additionally this method yields the path edges of each calculated shortest path. | ShortestPaths | ||
 | equals(o:Object):Boolean | YObject | |
[static]
Marks all edges that belong to a shortest path from start to end node. | ShortestPaths | ||
findShortestUniformPathsWithMaxDistance(graph:Graph, start:Node, targetMap:DataProvider, directed:Boolean, maxLength:int, pathEdges:EdgeList, pathNodes:NodeList):void [static]
Finds all nodes and edges that belong to a shortest path from start to a set of target nodes in the graph not farther away than a given distance. | ShortestPaths | ||
getClass():Class [override] | ShortestPaths | ||
| hashCode():int | YObject | |
[static]
This method finds the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs. | ShortestPaths | ||
[static]
A variant of kShortestPaths() that returns its result not as a list but as a special cursor that calculates the next path in the sequence only when needed. | ShortestPaths | ||
shortestPair(graph:Graph, source:Node, target:Node, directed:Boolean, costDP:DataProvider):Vector.<Object> [static]
Returns two edge-disjoint paths from in a nonnegatively-weighted directed graph, so that both paths connect s and t and have minimum total length. | ShortestPaths | ||
singleSource(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>):Boolean [static]
This method solves the single-source shortest path problem for arbitrary graphs. | ShortestPaths | ||
singleSource2(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):Boolean [static]
Like singleSource() but additionally this method yields the path edges of each calculated shortest path. | ShortestPaths | ||
singleSource3(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):Boolean [static]
Like singleSource2() but uses NodeMaps and DataProviders instead of arrays. | ShortestPaths | ||
singleSourceSingleSink(graph:Graph, s:Node, t:Node, directed:Boolean, cost:Vector.<Number>):EdgeList [static]
Similar to singleSourceSingleSink3() but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. | ShortestPaths | ||
[static]
Similar to singleSourceSingleSink4() but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. | ShortestPaths | ||
singleSourceSingleSink3(graph:Graph, s:Node, t:Node, directed:Boolean, cost:Vector.<Number>, pred:Vector.<Object>):Number [static]
This method solves the single-source single-sink shortest path problem for arbitrary graphs. | ShortestPaths | ||
singleSourceSingleSink4(graph:Graph, s:Node, t:Node, directed:Boolean, cost:DataProvider, pred:NodeMap):Number [static]
Like singleSourceSingleSink3() but uses NodeMaps and DataProviders instead of arrays. | ShortestPaths | ||
[static]
This method solves the single-source shortest path problem for arbitrary graphs where each edge has a uniform cost of 1.0. | ShortestPaths | ||
[static]
Like uniform() but additionally this method yields the path edges of each calculated shortest path. | ShortestPaths | ||
[static]
Like uniform2() but uses NodeMaps instead of arrays. | ShortestPaths | ||
uniformCost(graph:Graph):Vector.<Number> [static]
Convenience method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph. | ShortestPaths | ||
| ShortestPaths | () | Constructor |
Hide Inherited Public Methods
Show Inherited Public Methodspublic function ShortestPaths(init:Boolean = true)init:Boolean (default = true) |
| acyclic | () | method |
public static function acyclic(graph:Graph, s:Node, cost:Vector.<Number>, dist:Vector.<Number>):Boolean
This method solves the single-source shortest path problem for acyclic directed graphs.
Associated with each edge is an arbitrary double value that represents the cost of that edge. This method yields the shortest distance from a given node s to all other nodes.
Precondition GraphChecker.isAcyclic(graph)
Precondition cost.length == graph.E()
Precondition dist.length == graph.N()
Complexity O(graph.N()+graph.E())
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the start node for the shortest path search
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
dist:Vector.<Number> — return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
|
Boolean — false if the input graph was not acyclic.
|
| acyclic2 | () | method |
public static function acyclic2(graph:Graph, s:Node, cost:DataProvider, dist:NodeMap, pred:NodeMap):BooleanLike acyclicWithPaths() but uses NodeMaps and DataProviders instead of arrays.
Parameters
graph:Graph | |
s:Node | |
cost:DataProvider — must provide a double value for each edge.
| |
dist:NodeMap — return value. the map will provide a double value for each node.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
Boolean |
See also
| acyclicWithPaths | () | method |
public static function acyclicWithPaths(graph:Graph, s:Node, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):BooleanLike acyclic() but additionally this method yields the path edges of each calculated shortest path.
Precondition pred.length == graph.N()
Parameters
graph:Graph | |
s:Node | |
cost:Vector.<Number> | |
dist:Vector.<Number> | |
pred:Vector.<Object> — return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
|
Boolean |
See also
| allPairs | () | method |
public static function allPairs(graph:Graph, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Object>):Boolean
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.
Precondition cost.length == graph.E();
Precondition dimension of dist: [graph.N()][graph.N()]]
Complexity O(graph.N())*O(singleSource)
Parameters
graph:Graph — the graph being acted upon
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
dist:Vector.<Object> — return value that will hold the shortest path distances from all pairs of nodes s and t in the graph. The distance from s to t is dist[s.index()][t.index()]. If there is no path from s to t then dist[s.index()][t.index()] == Double.POSITIVE_INFINITY.
|
Boolean — whether or not the given graph contains a negative cost cycle.
|
| bellmanFord | () | method |
public static function bellmanFord(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>):Boolean
This method solves the single-source shortest path problem for arbitrary graphs.
Associated with each edge is an arbitrary double value that represents the cost of that edge. In case the given weighted graph contains no negative cost cycles this method will yield the shortest distance from a given node s to all other nodes. If, on the other hand, the given graph contains negative-cost cycles this method will yield no reasonable result which will be indicated by the return value false.
Precondition cost.length == graph.E()
Precondition dist.length == graph.N()
Complexity O(graph.E()*min(D,graph.N())) where D is the maximal number of edges in any shortest path.
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the start node for the shortest path search
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
dist:Vector.<Number> — return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
|
Boolean — false if this weighted graph contains a negative cost cycle, true otherwise.
|
| bellmanFordWithPath | () | method |
public static function bellmanFordWithPath(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):BooleanLike bellmanFord() but additionally this method yields the path edges of each calculated shortest path.
Precondition pred.length == graph.N()
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:Vector.<Number> | |
dist:Vector.<Number> | |
pred:Vector.<Object> — return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
|
Boolean |
See also
| bellmanFordWithPath2 | () | method |
public static function bellmanFordWithPath2(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):BooleanLike bellmanFordWithPath() but uses NodeMaps and DataProviders instead of arrays.
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:DataProvider — must provide a double value for each edge.
| |
dist:NodeMap — return value. the map will provide a double value for each node.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
Boolean |
See also
| constructEdgePath | () | method |
public static function constructEdgePath(s:Node, t:Node, pred:Vector.<Object>):EdgeListConvenience method that constructs an explicit edge path from the result yielded by one of the shortest paths methods defined in this class.
Parameters
s:Node — the start node of the shortest path. This must be the same start node that was specified when pred was calculated.
| |
t:Node — the end node of the path
| |
pred:Vector.<Object> — the shortest path edge result array returned by one of the shortest path edge methods defined in this class.
|
EdgeList — an edge list that holds the edges on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.
|
| constructEdgePath2 | () | method |
public static function constructEdgePath2(s:Node, t:Node, pred:DataProvider):EdgeListLike constructEdgePath() with the difference that the path edges are given by a DataProvider.
Parameters
s:Node | |
t:Node | |
pred:DataProvider — the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.
|
EdgeList |
See also
| constructNodePath | () | method |
public static function constructNodePath(s:Node, t:Node, pred:Vector.<Object>):NodeListConvenience method that constructs an explicit node path from the result yielded by one of the shortest paths methods defined in this class.
Parameters
s:Node — the start node of the shortest path. This must be the same start node that was specified when pred was calculated.
| |
t:Node — the end node of the path
| |
pred:Vector.<Object> — the shortest path edge result array returned by one of the shortest path edge methods defined in this class.
|
NodeList — a node list that holds the nodes on the shortest path from s to t in the correct order. If there is no path from s to t then an empty list is returned.
|
| constructNodePath2 | () | method |
public static function constructNodePath2(s:Node, t:Node, pred:DataProvider):NodeListLike constructNodePath() with the difference that the path edges are given by a DataProvider.
Parameters
s:Node | |
t:Node | |
pred:DataProvider — the shortest path edge result DataProvider returned by one of the shortest path edge methods defined in this class.
|
NodeList |
See also
| dijkstra | () | method |
public static function dijkstra(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>):void
This method solves the single-source shortest path problem for arbitrary graphs.
Associated with each edge is a non-negative double value that represents the cost of that edge. This method yields the shortest distance from a given node s to all other nodes.
Precondition For each edge e: cost[e.index()] >= 0
Precondition cost.length == graph.E()
Precondition dist.length == graph.N()
Complexity O(graph.E()+graph.N()*log(graph.N())
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the start node for the shortest path search
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
dist:Vector.<Number> — return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
|
| dijkstra2 | () | method |
public static function dijkstra2(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):voidLike dijkstraGetPaths() but uses NodeMaps and DataProviders instead of arrays.
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:DataProvider — must provide a double value for each edge.
| |
dist:NodeMap — return value. the map will provide a double value for each node.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
See also
| dijkstraGetPaths | () | method |
public static function dijkstraGetPaths(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):voidLike dijkstra() but additionally this method yields the path edges of each calculated shortest path.
Precondition pred.length == graph.N()
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:Vector.<Number> | |
dist:Vector.<Number> | |
pred:Vector.<Object> — return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
|
See also
| findShortestUniformPaths | () | method |
public static function findShortestUniformPaths(graph:Graph, start:Node, end:Node, directed:Boolean, pathMap:EdgeMap):void
Marks all edges that belong to a shortest path from start to end node.
This method assumes that each edge of the input graph has a cost of 1.0.
Complexity O(g.N()+g.E())
Parameters
graph:Graph — the input graph
| |
start:Node — the start node
| |
end:Node — the end node
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
pathMap:EdgeMap — the result. For each edge a boolean value will indicate whether or not it belongs to a shortest path connecting the two nodes.
|
| findShortestUniformPathsWithMaxDistance | () | method |
public static function findShortestUniformPathsWithMaxDistance(graph:Graph, start:Node, targetMap:DataProvider, directed:Boolean, maxLength:int, pathEdges:EdgeList, pathNodes:NodeList):void
Finds all nodes and edges that belong to a shortest path from start to a set of target nodes in the graph not farther away than a given distance.
This method assumes that each edge of the input graph has a cost of 1.0.
Complexity O(g.N()+g.E())
Complexity O(graph.N()+graph.E())
Parameters
graph:Graph — the input graph
| |
start:Node — the start node
| |
targetMap:DataProvider — a boolean data provider that marks the target nodes. If the data provider is null all nodes in the graph are assumed to be target nodes.
| |
directed:Boolean — whether or not to work on directed edges
| |
maxLength:int — the maximum edge length of the shortest paths. Shortest paths that are longer than this value will not be considered.
| |
pathEdges:EdgeList — a return value. If this parameter is not null, this algorithm first clears the list and then adds all edges that belong to the detected shortest paths.
| |
pathNodes:NodeList — a return value. If this parameter is not null, this algorithm first clears the list and then adds all nodes that belong to the detected shortest paths.
|
| getClass | () | method |
override public function getClass():ClassReturnsClass |
| kShortestPaths | () | method |
public static function kShortestPaths(graph:Graph, costDP:DataProvider, start:Node, end:Node, k:int):YList
This method finds the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.
The result will be returned as a list of EdgeList objects. Note that the returned paths are not required to be simple, i.e. they may contain a node or an edge multiple times.
Precondition For each edge e: costDP.getDouble(e) >= 0
Complexity O(graph.E() + graph.N()*log(graph.N()) + k)
Parameters
graph:Graph — the graph being acted upon
| |
costDP:DataProvider — a data provider that provides a double-valued cost for each edge of the input graph.
| |
start:Node — start node of the shortest paths
| |
end:Node — the end node of the shortest paths
| |
k:int |
YList — a list of EdgeList objects each of which representing a path from start to end node. The i-th path in the list contains the i-th shortest path between start and end node. Note that the returned list may contain less than k paths in case there are fewer directed paths between start and end node.
|
| kShortestPathsCursor | () | method |
public static function kShortestPathsCursor(graph:Graph, costDP:DataProvider, start:Node, end:Node, k:int):YCursorA variant of kShortestPaths() that returns its result not as a list but as a special cursor that calculates the next path in the sequence only when needed. The returned cursor only supports the operation com.yworks.yfiles.base.YCursor.ok(), com.yworks.yfiles.base.YCursor.current() and com.yworks.yfiles.base.YCursor.next() .
Parameters
graph:Graph | |
costDP:DataProvider | |
start:Node | |
end:Node | |
k:int |
YCursor |
See also
| shortestPair | () | method |
public static function shortestPair(graph:Graph, source:Node, target:Node, directed:Boolean, costDP:DataProvider):Vector.<Object>
Returns two edge-disjoint paths from in a nonnegatively-weighted directed graph, so that both paths connect s and t and have minimum total length.
Parameters
graph:Graph — the graph being acted upon
| |
source:Node — source node of the shortest pair
| |
target:Node — end node of the shortest pair
| |
directed:Boolean — whether or not to interpret the edges as directed or undirected
| |
costDP:DataProvider — a data provider that provides a double-valued cost for each edge of the input graph.
|
Vector.<Object> — a two-dimensional EdgeList array that holds the resulting edge-disjoint paths, or null if no such edge-disjoint paths exist.
|
| singleSource | () | method |
public static function singleSource(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>):BooleanThis method solves the single-source shortest path problem for arbitrary graphs. Depending on the structure of the given graph and the values of the given edge costs it delegates its job to the algorithm with the theoretically best running time. Please note that theory does not necessarily reflect practice.
Precondition cost.length == graph.E()
Precondition dist.length == graph.N()
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the start node for the shortest path search
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
dist:Vector.<Number> — return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
|
Boolean — false if this weighted graph contains a negative cost cycle, true otherwise.
|
| singleSource2 | () | method |
public static function singleSource2(graph:Graph, s:Node, directed:Boolean, cost:Vector.<Number>, dist:Vector.<Number>, pred:Vector.<Object>):BooleanLike singleSource() but additionally this method yields the path edges of each calculated shortest path.
Precondition pred.length == graph.N()
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:Vector.<Number> | |
dist:Vector.<Number> | |
pred:Vector.<Object> — return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
|
Boolean |
See also
| singleSource3 | () | method |
public static function singleSource3(graph:Graph, s:Node, directed:Boolean, cost:DataProvider, dist:NodeMap, pred:NodeMap):BooleanLike singleSource2() but uses NodeMaps and DataProviders instead of arrays.
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
cost:DataProvider — must provide a double value for each edge.
| |
dist:NodeMap — return value. the map will provide a double value for each node.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
Boolean |
See also
| singleSourceSingleSink | () | method |
public static function singleSourceSingleSink(graph:Graph, s:Node, t:Node, directed:Boolean, cost:Vector.<Number>):EdgeListSimilar to singleSourceSingleSink3() but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. If the returned path is empty then there is no path between the nodes.
Parameters
graph:Graph | |
s:Node | |
t:Node | |
directed:Boolean | |
cost:Vector.<Number> |
EdgeList — a shortest path between source and sink
|
See also
| singleSourceSingleSink2 | () | method |
public static function singleSourceSingleSink2(graph:Graph, s:Node, t:Node, directed:Boolean, cost:DataProvider):EdgeListSimilar to singleSourceSingleSink4() but instead of returning the shortest distance between the source and sink the actual shortest edge path between these nodes will be returned. If the returned path is empty then there is no path between the nodes.
Parameters
graph:Graph | |
s:Node | |
t:Node | |
directed:Boolean | |
cost:DataProvider |
EdgeList — a shortest path between source and sink
|
See also
| singleSourceSingleSink3 | () | method |
public static function singleSourceSingleSink3(graph:Graph, s:Node, t:Node, directed:Boolean, cost:Vector.<Number>, pred:Vector.<Object>):Number
This method solves the single-source single-sink shortest path problem for arbitrary graphs.
Associated with each edge is a non-negative double value that represents the cost of that edge. This method returns the shortest distance from node s to node t. It also returns information to construct the actual path between these to nodes.
Precondition For each edge e: cost[e.index()] >= 0
Precondition cost.length == graph.E()
Precondition pred.length == graph.N()
Complexity O(graph.E()+graph.N()*log(graph.N())
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the source node for the shortest path search
| |
t:Node — the sink node for the shortest path search
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
cost:Vector.<Number> — holds the costs for traversing each edge. Edge e has cost cost[e.index()].
| |
pred:Vector.<Object> — return value that holds for each node v on the the shortest the path from s to t an edge pred[v.index()] which is the last edge on the shortest path from s to v. If v == s or if there is no shortest path from s to v then pred[v.index()] == null.
|
Number — the distance between s and t if a path between these two nodes exist and Double.POSITIVE_INFINITY otherwise.
|
See also
| singleSourceSingleSink4 | () | method |
public static function singleSourceSingleSink4(graph:Graph, s:Node, t:Node, directed:Boolean, cost:DataProvider, pred:NodeMap):NumberLike singleSourceSingleSink3() but uses NodeMaps and DataProviders instead of arrays.
Parameters
graph:Graph | |
s:Node | |
t:Node | |
directed:Boolean | |
cost:DataProvider — must provide a double value for each edge.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
Number |
See also
| uniform | () | method |
public static function uniform(graph:Graph, s:Node, directed:Boolean, dist:Vector.<Number>):void
This method solves the single-source shortest path problem for arbitrary graphs where each edge has a uniform cost of 1.0.
This method yields the shortest distance from a given node s to all other nodes.
Precondition dist.length == graph.N()
Complexity O(graph.N()+graph.E())
Parameters
graph:Graph — the graph being acted upon
| |
s:Node — the start node for the shortest path search
| |
directed:Boolean — whether or not to consider the graph as directed. If the graph is to be considered undirected then each edge can be traversed in both directions and the returned shortest paths can thus be undirected.
| |
dist:Vector.<Number> — return value that will hold the shortest distance from node s to all other nodes. The distance from s to v is dist[v.index()]. If there is no path from s to v then dist[v.index()] == Double.POSITIVE_INFINITY.
|
| uniform2 | () | method |
public static function uniform2(graph:Graph, s:Node, directed:Boolean, dist:Vector.<Number>, pred:Vector.<Object>):voidLike uniform() but additionally this method yields the path edges of each calculated shortest path.
Precondition pred.length == graph.N()
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
dist:Vector.<Number> | |
pred:Vector.<Object> — return value that holds for each node t the shortest path edge pred[t.index()] which is the last edge on the shortest path from s to t. If t == s or if there is no shortest path from s to t then pred[t.index()] == null.
|
See also
| uniform3 | () | method |
public static function uniform3(graph:Graph, s:Node, directed:Boolean, dist:NodeMap, pred:NodeMap):voidLike uniform2() but uses NodeMaps instead of arrays.
Parameters
graph:Graph | |
s:Node | |
directed:Boolean | |
dist:NodeMap — return value. the map will provide a double value for each node.
| |
pred:NodeMap — return value. the map will provide an Edge for each node.
|
See also
| uniformCost | () | method |
public static function uniformCost(graph:Graph):Vector.<Number>
Convenience method that returns an array containing uniform edge costs of 1.0 for each edge of the given graph.
Parameters
graph:Graph |
Vector.<Number> — an array cost[] that contains uniform edge costs of 1.0 for each edge e: cost[e.index()] == 1.0.
|