Paths

A path is a sequence of edges that connect a sequence of nodes. Typically, a path does not contain cycles. The length of a path (or the distance between its start and end nodes) is the sum of the costs of the edges. If no costs are provided, the length is simply the number of edges.

Shortest Path

A shortest path between two nodes is a path with the minimum cost.

In Finding the shortest path, the numbers on the edges represent the costs associated with traversing the edge. To travel from Start to Destination with the lowest cost, follow the emphasized edges. These edges define the shortest path between the two nodes, with a total cost of 8 units.

Running single-source single-sink shortest path shows the code that prepares and runs a single-source, single-sink Shortest Path algorithm on the graph 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: new Arrow(ArrowType.STEALTH)
})
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), and in a directed graph (right).

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

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

Running single-source shortest paths shows the code to prepare and run a single-source shortest paths algorithm on the graph 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 calculate the shortest paths between multiple source and multiple sink nodes, Paths calculates all simple paths between start and end nodes.

Reachability

The Reachability algorithm identifies all nodes that can be reached from the specified startNodes by following a path.

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

Running the reachability algorithm shows the code to prepare and run the Reachability algorithm to find nodes reachable via 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, but this time the blue nodes are reachable from the green start node by following an undirected path.