shortestpath: Find Shortest Path using Floyd-Warshall Algorithm In maotai: Tools for Matrix Algebra, Optimization and Inference

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

  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 Feb. 3, 2022, 5:09 p.m.