Shortest paths, k-shortest paths and travelling salesman tours

ShortestPath: Dijkstra (1959) on a directed graph given as (from, to, cost) rows with nodes 1..n; the unsettled node of least distance (lowest index on ties) is settled next. KShortestPaths: Yen's (1971) loopless k shortest paths. TspTour: Held-Karp exact tour (up to 12 nodes under "auto") or nearest neighbour plus 2-opt, starting at node 1. Identical to the Python arm morie.fn.transnet (which numbers nodes from 0).

Usage

ShortestPath(n, edges, source, target = NULL)

KShortestPaths(n, edges, source, target, k)

TspTour(D, method = "auto")

Arguments

n

Number of nodes.

edges

Matrix of from, to, cost.

source, target

Nodes.

k

Number of paths.

D

Distance matrix.

method

"auto", "exact" or "heuristic".

Value

List.

References

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269-271.

Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. Management Science 17, 712-716.

Held, M. and Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196-210.

Examples

ShortestPath(4, rbind(c(1, 2, 1), c(2, 3, 2), c(1, 3, 4), c(3, 4, 1)), 1, 4)$path
#> [1] 1 2 3 4
TspTour(rbind(c(0, 2, 9, 10), c(1, 0, 6, 4), c(15, 7, 0, 8), c(6, 3, 12, 0)))$length
#> [1] 21