Finds shortest paths between pairs of multiple sources and sinks.
Remarks
The shortest paths will be determined by invoking a single-source shortest path search for each node in sources. For n sources and m sinks the result thus may contain up to n ⋅ m distinct paths.
Other Shortest Path Algorithms
yFiles for HTML supports a number of other algorithms that compute shortest paths in a graph:
- ShortestPath – finds the shortest path between two nodes
- SingleSourceShortestPaths – finds shortest paths from a single source node to several other nodes
Other Path-Related Algorithms
yFiles for HTML also supports a number of other algorithms related to paths in a graph:
- Paths – finds all paths between a set of source and a set of target nodes
- Chains – finds all chains, that is, sequences of nodes that are each connected with just an edge without branches
- Cycle – finds a cycle if one exists
- LongestPath – finds the longest path in the graph
Examples
Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.AllPairsShortestPaths
See Also
Constructors
Creates a new AllPairsShortestPaths instance.
Parameters
A map of options to pass to the method.
- sources - ItemCollection<INode>
A collection of source (start) nodes. This option sets the sources property on the created object.
- sinks - ItemCollection<INode>
A collection of sink (end, target) nodes. This option sets the sinks property on the created object.
- costs - ItemMapping<IEdge,number>
A mapping for the cost for traversing an edge. This option sets the costs property on the created object.
- directed - boolean
A value indicating whether edge direction should be considered. This option sets the directed property on the created object.
- subgraphNodes - ItemCollection<INode>
The collection of nodes which define a subset of the graph for the algorithms to work on. This option sets the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
The collection of edges which define a subset of the graph for the algorithms to work on. This option sets the subgraphEdges property on the created object.
Properties
Gets or sets a mapping for the cost for traversing an edge.
Remarks
For the shortest path algorithm this is a measure of the edge's length, so more expensive (higher cost) edges are considered longer and avoided if there's a shorter (cheaper) path elsewhere in the graph.
When no costs are provided, uniform costs of 1
are assumed for all edges. This makes a shortest path the path with the fewest edges.
Negative costs are supported only for directed graphs and only if there is no cycle with negative costs. Negative costs are not supported for undirected graphs. run will throw an InvalidOperationError in these cases.
Examples
Gets or sets a collection of sink (end, target) nodes.
Remarks
Examples
// the sink nodes are provided as collection (the selected nodes)
algorithm = new AllPairsShortestPaths({
sinks: graphComponent.selection.selectedNodes
})
// the sink nodes are the nodes in the graph for which the delegate returns true
// (nodes in the graph with "sink" as tag)
algorithm = new AllPairsShortestPaths({
sinks: (node) => node.tag === 'sink'
})
See Also
Gets or sets a collection of source (start) nodes.
Remarks
Examples
// the source nodes are provided as collection (the selected nodes)
algorithm = new AllPairsShortestPaths({
sources: graphComponent.selection.selectedNodes
})
// the source nodes are the nodes in the graph for which the delegate returns true
// (nodes in the graph with "source" as tag)
algorithm = new AllPairsShortestPaths({
sources: (node) => node.tag === 'source'
})
See Also
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all edges of the graph will be processed.
If only the excludes are set all edges in the graph except those provided in the excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all nodes of the graph will be processed.
If only the excludes are set all nodes in the graph except those provided in the excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
Methods
Finds all shortest paths between pairs of nodes from sources and sinks.
Returns
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.