shortestpath: Find Shortest Path using Floyd-Warshall Algorithm

In maotai: Tools for Matrix Algebra, Optimization and Inference

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)

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

## 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 March 31, 2023, 6:48 p.m.