Skip to contents

Solve for Shortest Path from Source Node to All Other Nodes

Source: R/shortestpath.R
ShortestPathFromSource.Rd

Finds the shortest path from a source node to the rest of the nodes in a directed graph. These shortest path algorithms consider the distances present in the graph, as well as the number of edges.

Usage

ShortestPathFromSource(
  arcSources,
  arcTargets,
  arcDistances,
  numNodes,
  sourceNode,
  algorithm = "Dijkstra"
)

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 source node

algorithm

Choices of algorithm include "Dijkstra" and "BellmanFord". "Dijkstra" is the default.

Value

A named list containing two entries: 1) "distances": the distances from each node to the startNode and 2) "predecessors": the predecessor of each vertex in its shortest path.

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.