shortestpath: Find Shortest Path using Floyd-Warshall Algorithm

Description Usage Arguments Value References Examples

View source: R/shortestpath.R

Description

This is a fast implementation of Floyd-Warshall algorithm to find the shortest path in a pairwise sense using RcppArmadillo. A logical input is also accepted. The given matrix should contain pairwise distance values d_{i,j} where 0 means there exists no path for node i and j.

Usage

1

Arguments

dist

either an (n\times n) matrix or a dist class object.

Value

an (n\times n) matrix containing pairwise shortest path length.

References

\insertRef

floyd_algorithm_1962maotai

\insertRef

warshall_theorem_1962maotai

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
## simple example : a ring graph
#  edges exist for pairs
A = array(0,c(10,10))
for (i in 1:9){
  A[i,i+1] = 1
  A[i+1,i] = 1
}
A[10,1] <- A[1,10] <- 1

# compute shortest-path and show the matrix
sdA <- shortestpath(A)

# visualize
opar <- par(no.readonly=TRUE)
par(pty="s")
image(sdA, main="shortest path length for a ring graph")
par(opar)

maotai documentation built on Oct. 25, 2021, 9:06 a.m.