aux.shortestpath {Rdimtools}

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.

Usage

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

Author(s)

Kisung You

References

Floyd, R.W. (1962) Algorithm 97: Shortest Path. Commincations of the ACMS, Vol.5(6):345.

Examples

## generate a toy data
X = aux.gensamples(n=10)

## Find knn graph with k=5
Xgraph = aux.graphnbd(X,type=c("knn",5))

## Separately use binarized and real distance matrices
W1 = aux.shortestpath(Xgraph$mask)
W2 = aux.shortestpath(Xgraph$dist)

## visualize
opar <- par(no.readonly=TRUE)
par(mfrow=c(1,2), pty="s")
image(W1, main="from binarized")
image(W2, main="from Euclidean distance")
par(opar)