maotai (version 0.2.5)

shortestpath: Find Shortest Path using Floyd-Warshall Algorithm

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

shortestpath(dist)

Value

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

Arguments

dist

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

References

floyd_algorithm_1962maotai

warshall_theorem_1962maotai

Examples

## 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)