Finds the shortest path between two nodes (also known as the single-source single-sink shortest path problem).
Remarks
The shortest path will be determined either by Dijkstra's algorithm, or an implementation of A*, depending on whether a heuristic exists for estimating the remaining distance between a node and the sink node.
Other Shortest Path Algorithms
yFiles for HTML supports a number of other algorithms that compute shortest paths in a graph:
- SingleSourceShortestPaths – finds shortest paths from a single source node to several other nodes
- AllPairsShortestPaths – finds all shortest paths between pairs of several source and sink 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
// configure the shortest path algorithm
const algorithm = new ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// 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
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}// configure the shortest path algorithm
const algorithm = new ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// 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
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.ShortestPath
See Also
Constructors
Creates a new ShortestPath instance.
Parameters
A map of options to pass to the method.
- source - SingleItem<INode>
The source (start) node of the path. This option sets the source property on the created object.
- sink - SingleItem<INode>
The sink (end, target) node of the path. This option sets the sink 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.
- heuristic - function(INode, INode):number
A function that estimates the distance between two nodes. This option sets the heuristic property on the created object.
Signature Details
function(arg1: INode, arg2: INode) : numberEncapsulates a method that has two parameters and returns a value of the type specified by theTResultparameter.Parameters
- arg1 - INode
- The first parameter of the method that this delegate encapsulates.
- arg2 - INode
- The second parameter of the method that this delegate encapsulates.
Returns
- number
- The return value of the method that this delegate encapsulates.
- 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.
The costs must not be negative.
When no costs are provided, uniform costs of 1 are assumed for all edges. This makes the shortest path the path with the fewest edges.
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()// 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 function that estimates the distance between two nodes.
Remarks
This can be used to speed up the shortest path search by internally switching to an A* implementation which can skip large parts of the graph that would lead further away from the target node.
A heuristic must be admissible, that is, it must never overestimate the remaining distance to the target. Otherwise the found path may not be the shortest one.
The heuristic ties closely into the costs, as both should use the same, or similar measures. For example, if the costs are defined by the actual visual length of an edge, the heuristic can be Euclidean distance between the two nodes because that's a useful estimate of the remaining distance when the costs are defined that way.
Don't use a heuristic if there is no useful and quick way of estimating the remaining distance.
The second node passed to the function is always the sink node as the remaining distance is only ever estimated towards the sink node.
Signature Details
function(arg1: INode, arg2: INode) : number
TResult parameter.Parameters
- arg1 - INode
- The first parameter of the method that this delegate encapsulates.
- arg2 - INode
- The second parameter of the method that this delegate encapsulates.
Returns
- number
- The return value of the method that this delegate encapsulates.
Gets or sets the sink (end, target) node of the path.
Examples
// the item is the explicitly set item (the end node)
algorithm = new ShortestPath({
sink: endNode
})
// the item is the first item in the source (the first selected node)
algorithm = new ShortestPath({
sink: graphComponent.selection.selectedNodes
})
// the item is the first in the graph for which the predicate returns true
// (the first node in the graph with "sink" as tag)
algorithm = new ShortestPath({
sink: (node) => node.tag === 'sink'
})Gets or sets the source (start) node of the path.
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.selectedNodes
})
// 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 ShortestPath({
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 ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge) =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow === IArrow.NONE
}
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}// configure the shortest path algorithm
const algorithm = new ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow === IArrow.NONE
}
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.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 ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node) =>
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 edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}// configure the shortest path algorithm
const algorithm = new ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
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 edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}const subset = new ItemCollection(
graphComponent.selection.selectedNodes
)const subset = new ItemCollection()
subset.excludes = (n) => graph.isGroupNode(n)const subset = new ItemCollection<INode>()
subset.excludes = (n) => graph.isGroupNode(n)const subset = new ItemCollection(
graphComponent.selection.selectedNodes,
(n) => graph.isGroupNode(n)
)Methods
Finds the shortest path between source and sink.
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 ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// 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
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}// configure the shortest path algorithm
const algorithm = new ShortestPath({
// single source - single sink
source: startNode,
sink: endNode,
// 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
const result = algorithm.run(graph)
// highlight the edge path
for (const edge of result.edges) {
graph.setStyle(edge, highlightPathStyle)
}