Finds the shortest path between one node and multiple other nodes in the graph (also known as the single-source shortest path problem).
Remarks
The shortest paths will be determined either by the Bellman-Ford algorithm or Dijkstra's algorithm, depending on whether or not edge costs are provided and the exact values of those edge costs.
Other Shortest Path Algorithms
@PRODUCT@ supports a number of other algorithms that compute shortest paths in a graph:
- ShortestPath – finds the shortest path between two nodes
- AllPairsShortestPaths – finds all shortest paths between pairs of several source and sink nodes
Other Path-Related Algorithms
@PRODUCT@ 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
// configure the shortest path algorithm
const algorithm = new SingleSourceShortestPaths({
// single source
source: startNode,
// add edge cost mapping which returns the actual length of the edge
costs: (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength(),
})
// run the algorithm:
// calculate paths from startNode to all nodes in the graph
const result = algorithm.run(graph)
// for each end node
for (const targetNode of targetNodes) {
// set its distance to the startNode as label text
graph.setLabelText(
targetNode.labels.get(0),
`${result.getPathTo(targetNode)!.distance}`,
)
// and mark the edge path from start to the end node
for (const edge of result.getPathTo(targetNode)!.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}Type Details
- yFiles module
- view-layout-bridge
See Also
Constructors
Parameters
A map of options to pass to the method.
- source - ItemCollection<INode>
- The source (start) node. This option either sets the value directly or recursively sets properties to the instance of the source property on the created object.
- sinks - ItemCollection<INode>
- A collection of sink (end, target) nodes. This option either sets the value directly or recursively sets properties to the instance of the sinks property on the created object.
- costs - ItemMapping<IEdge,number>
- A mapping for the cost of traversing an edge. This option either sets the value directly or recursively sets properties to the instance of 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 either sets the value directly or recursively sets properties to the instance of 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 either sets the value directly or recursively sets properties to the instance of the subgraphEdges property on the created object.
Properties
Gets or sets a mapping for the cost of 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
// setting the cost for traversing e1 and e2 to 1.0
algorithm.costs.mapper.set(e1, 1.0)
algorithm.costs.mapper.set(e2, 1.0)
// all other edges are not set and return 0// returns the length of the actual edge path as cost
algorithm.costs = (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength()Gets or sets a collection of sink (end, target) nodes.
Remarks
The algorithm always finds paths from source to all nodes. However, this collection affects which individual paths are returned in the result.
For a result that's typical of single-source shortest path algorithms, the complete graph would be included here. If this collection is empty, no paths will be returned in the result.
Examples
// the sink nodes are provided as collection (the selected nodes)
algorithm = new SingleSourceShortestPaths({
sinks: graphComponent.selection.nodes,
})
// 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 SingleSourceShortestPaths({
sinks: (node) => node.tag === 'sink',
})Gets or sets the source (start) node.
Remarks
Examples
// the item is the explicitly set item (the start node)
algorithm = new ShortestPath({
source: startNode,
})
// the item is the first item in the source (the first selected node)
algorithm = new ShortestPath({
source: graphComponent.selection.nodes,
})
// the item is the first in the graph for which the predicate returns true
// (the first node in the graph with "source" as tag)
algorithm = new SingleSourceShortestPaths({
source: (node) => node.tag === 'source',
})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
// configure the shortest path algorithm
const algorithm = new SingleSourceShortestPaths({
// single source - single sink
source: startNode,
sinks: targetNodes,
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge path
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}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
// configure the shortest path algorithm
const algorithm = new SingleSourceShortestPaths({
// single source - single sink
source: startNode,
sinks: targetNodes,
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge path
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}algorithm.subgraphNodes = graphComponent.selection.nodesalgorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)Methods
Finds the shortest paths between source and sinks.
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input graph to run the algorithm on.
Returns
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Examples
// configure the shortest path algorithm
const algorithm = new SingleSourceShortestPaths({
// single source
source: startNode,
// add edge cost mapping which returns the actual length of the edge
costs: (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength(),
})
// run the algorithm:
// calculate paths from startNode to all nodes in the graph
const result = algorithm.run(graph)
// for each end node
for (const targetNode of targetNodes) {
// set its distance to the startNode as label text
graph.setLabelText(
targetNode.labels.get(0),
`${result.getPathTo(targetNode)!.distance}`,
)
// and mark the edge path from start to the end node
for (const edge of result.getPathTo(targetNode)!.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}