Compute Shortest Path Distance Matrix for Georeferenced Points

Download data and R Code for this example

Project Requirement:

Given a set of spatially-referenced point locations throughout a region,
compute the matrix of shortest-path distances between each possible pair of points.

Input Data / Format:

Point File: USGS Hydrologic Unit Code (HUC4) Polygon Centroids- ESRI Polygon Shapefile (HUC4 Centroid Points in BLUE)

 InputPoints image

1) Read the input centroid point file into an R Spatial Points Data Frame.

2) Compute the Shortest Path Distance between each unique point pair.

3) Write the resulting shortest path matrix to a Comma-Separated Value (CSV) file.


To review and run this example:

1) Download the Zip file archive, unpack into a folder.

2) Be sure that your R (version 2.9.2 or later) environment includes the sp and rgdal packages.

3) Start R, set working directory to the folder containing the downloaded and unpacked example.

4) At command prompt, enter 'source("./CalcShortestPathMatrix.r")'.

5) Enter the command: 'CalcShortestPathMatrix("NewHuc4Centroids","NewShortestPathMatrix")'

6) Open the output file 'NewShortestPathMatrix.csv'. Since distances between point pairs
are symmetrical (the same in both directions), only the lower triangular of the matrix contains distance values.


 Shortest Path Matrix Image

R Script:

# rgdal loads sp


# Compute the inter-centroid distance matrix
# initial state: main diagonal = 0, other cells = NA
Centroids <- readOGR(".",pointShapeFileRoot)
nPoints <- length(Centroids$X)
distMat <- matrix(NA, nrow=nPoints, ncol=nPoints)
for (i in 1:nPoints) distMat[i,i] = 0

# Distance matrices are symmetric, therefore we only need to fill in the lower triangle.
# Here is one way to do so:

for (i in 2:nPoints) {
 j <- i-1  
 distMat[i,1:j] <- spDistsN1(cbind(Centroids$X[1:j],Centroids$Y[1:j]),
                                        cbind(Centroids$X[i],Centroids$Y[i]),longlat = TRUE)
colnames(distMat) <- rownames(distMat) <- seq_len(nPoints)
write.csv(distMat ,paste(distanceMatrixFileRoot,"csv",sep="."))

Learning More:

The GIS Primer: The Nature of Spatial Information

Overview: Euclidean Shortest-Path Calculations