Skip to contents

FINDS the shortest arc disjoint paths between two nodes in a directed graph. This implementation runs a variation of the successive shortest path algorithm.

Usage

ShortestPath(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  sourceNode,
  destNode,
  algorithm = "Suurballe"
)

Arguments

arcSources

Vector corresponding to the source nodes of a graph's edges

arcTargets

Vector corresponding to the destination nodes of a graph's edges

arcDistances

Vector corresponding to the distances of a graph's edges

numNodes

The number of nodes in the graph

sourceNode

The start node of the path

destNode

The end node of the path

algorithm

Choices of algorithm include "Suurballe". "Suurballe" is the default.

Value

A named list containing two entries: 1) "num_paths": the number of paths from the start node to the end node and 2) "list_paths": a list of paths found. If there are multiple paths, then the second entry will have multiple paths.

Details

For details on LEMON's implementation, including differences between the algorithms, see https://lemon.cs.elte.hu/pub/doc/1.3.1/a00609.html.