C

SingleSourceShortestPathsResult

Show Usages
Represents all shortest paths between a single source node and multiple sink nodes in a graph as computed by SingleSourceShortestPaths.
Inheritance Hierarchy

Remarks

This class cannot be instantiated

Members

No filters for this type

Properties

distances

: ResultItemMapping<INode, number>
readonly
Gets a mapping from each node to its shortest distance from the SingleSourceShortestPaths.source node.

Since every shortest path consists of other shortest paths, this mapping not only contains the shortest distances to the sink nodes but also all nodes on the paths to the sinks.

The distance to a node is Number.POSITIVE_INFINITY if there is no path from SingleSourceShortestPaths.source to that node.

readonlyfinal

Examples

const algorithm = new SingleSourceShortestPaths({
  source: startNode,
  sinks: targetNodes,
})
const result = algorithm.run(graph)
for (const node of targetNodes) {
  graph.setLabelText(
    node.labels.get(0),
    `Distance: ${result.distances.get(node)}`,
  )
}

paths

: ResultItemCollection<Path>
readonly
Gets a collection of shortest paths between the SingleSourceShortestPaths.source node and sink nodes.

This collection contains every existing shortest path between SingleSourceShortestPaths.source and the sink nodes. This means that there may well be fewer paths than sinks if some of them are not reachable from the source node.

While the underlying algorithm always computes shortest paths to all nodes in the graph, this collection only contains paths to the initially configured sink nodes.

readonlyfinal

predecessors

: ResultItemMapping<INode, IEdge>
readonly
Gets a mapping from each node to the last incoming edge of the shortest path to this node.

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 have no path from SingleSourceShortestPaths.source.

readonlyfinal

Examples

Starting with a target (sink) node one can walk along the edges to the start node.
// 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
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)
}

See Also

Developer's Guide

Methods

getPathTo

(sink: INode): Path
Gets the shortest path from the configured SingleSourceShortestPaths.source node to the given sink node if one exists.
If sink was not part of the SingleSourceShortestPaths.sinks collection or no path between SingleSourceShortestPaths.source and sink exists, the return value is null.
final

Parameters

sink: INode
The sink (target, end) node of the path to get.

Return Value

Path
The shortest path between the source and the sink node.

See Also

Developer's Guide