Paths

A path is a (usually cycle-free) sequence of edges that connect a sequence of nodes. The length of such a path (respectively the distance between its start and end nodes) is the sum of the costs of the edges, or the edge count if no costs are provided.

Shortest Path

A shortest path between two nodes is one of the paths with minimum costs.

In Finding the shortest path the numbers at the edges denote the costs that are associated with the traversal of an edge. To get from Start to Destination with minimum costs results in the path of emphasized edges. These edges define the shortest path between the two nodes with an accumulated cost of 8 [units].

Running single-source single-sink shortest path shows the code to prepare and run a single-source single-sink Shortest Path algorithm on the graph depicted in Finding the shortest path.

// configure and run the single-source single-sink algorithm on the graph
const shortestPathResult = new ShortestPath({
  source: startNode,
  sink: endNode,
  directed: true,
  costs: (edge) => getEdgeCost(edge)
}).run(graph)
// emphasis the path edges
const pathEdgeStyle = new PolylineEdgeStyle({
  stroke: new Stroke('black', 2.0),
  targetArrow: IArrow.DEFAULT
})
shortestPathResult.edges.forEach((edge) => graph.setStyle(edge, pathEdgeStyle))

The image below depicts the result of a shortest path algorithm in a uniform, undirected graph (left), with weights assigned to the edges (middle), or in a directed graph (right).

Finding the shortest paths from a starting node shows the shortest paths from Start to all other nodes from the graph known as SingleSourceShortestPaths problem.

Following the emphasized predecessor edges from the destination node of each of these paths to the Start forms the shortest path to the destination.

Running single-source shortest paths shows the code to prepare and run a single-source shortest paths algorithm on the graph depicted in Finding the shortest path.

// configure and run the single-source shortest path algorithm on the graph
const singleSourceShortestPath = new SingleSourceShortestPaths({
  source: startNode,
  directed: true,
  costs: (edge) => getEdgeCost(edge)
}).run(graph)
// access all or specific shortest paths
const allShortestPathsFromSource = singleSourceShortestPath.paths
const pathToDestination = singleSourceShortestPath.getPathTo(destination)

While AllPairsShortestPaths can be used to calculate the shortest paths between multiple source and multiple sink nodes, Paths calculates all simple path between start and end nodes.

Reachability

The Reachability algorithm calculates all nodes that can be reached via a path from the specified startNodes.

Colored reachable nodes via directed paths shows a graph where all blue nodes are reachable by a directed path from the green start node.

Running the reachability algorithm shows the code to prepare and run the Reachability algorithm for directed paths resulting in the graph depicted in Colored reachable nodes via directed paths.

const reachabilityResult = new Reachability({
  directed: true,
  startNodes: greenNode
}).run(graph)
reachabilityResult.reachableNodes.forEach((node) => setBlueNodeStyle(node))

Colored reachable nodes via undirected paths shows the same graph where all blue nodes are reachable by an undirected path from the green start node.