Represents the shortest path between two nodes in a graph as computed by ShortestPath.
Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.ShortestPathResult
Properties
Gets the distance of the path.
Remarks
This is the sum of edge costs along the path. If there are no edge costs, the distance is the number of edges in the path.
If there is no path between the two nodes, this is equal to Number.POSITIVE_INFINITY.
Examples
algorithm.source = startNode
algorithm.sink = endNode
const result = algorithm.run(graph)
console.log(result.distance) // the distance between startNode and endNodeGets a mapping from each node to the last incoming edge of the shortest path to this node.
Remarks
This is a common representation of a shortest path tree which exploits the fact that any shortest path in a graph has sub-paths that themselves are also shortest paths. A shortest path to a given node can be reconstructed backwards by querying this mapping for that node, following the returned edge to its source node, and continuing to query the mapping until the source node of the shortest-path search is reached.
This mapping returns null for nodes that are not part of the found shortest path.
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
const predResultsMap = result.predecessors
let walker = endNode
let edge = predResultsMap.get(walker)
while (edge !== null) {
graph.setStyle(edge, highlightPathStyle)
walker = edge.opposite(walker)
edge = predResultsMap.get(walker)
}// 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
const predResultsMap = result.predecessors
let walker: INode = endNode
let edge: IEdge | null = predResultsMap.get(walker)
while (edge !== null) {
graph.setStyle(edge, highlightPathStyle)
walker = edge.opposite(walker) as INode
edge = predResultsMap.get(walker)
}