locationgamer (version 0.1.0)

dijkstra: Shortest path through network using dijkstra's algorithm

Description

This function finds the shortest path from a starting node to an end node in a network specified by an edge matrix and vertex coordinates. Position i,j of the edge matrix is one if there is an edge between the ith and jth vertex, zero otherwise. The function returns the path NA with length infinity if the network is disconnected, i.e. if no shortest path can be found.

Usage

dijkstra(edgeMatrix, coordMatrix, initialNode, endNode, nNodes)

Arguments

edgeMatrix

A square matrix consisting of zeros and ones. Has to be zero on the diagonals

coordMatrix

A data frame containing the x and y coordinates of each network vertex

initialNode

A number corresponding to the start node/ vertex

endNode

A number corresponding to the end node/ vertex

nNodes

The number of vertices/ nodes in the network

Value

A list consisting of a vector with the vertices/ nodes visited by the shortest path and the length of the shortest path.

Examples

# NOT RUN {
initialNode <- 1
endNode <- 4
nNodes <- 4
edgeMatrix <- matrix(0, nrow = 4, ncol = 4)
edgeMatrix[,1] <- c(0,1,0,0)
edgeMatrix[,2] <- c(1,0,1,1)
edgeMatrix[,3] <- c(0,1,0,0)
edgeMatrix[,4] <- c(0,1,0,0)
coordMatrix <- matrix(c(0,10,15,20,30,30,15,15),ncol = 2)
dijkstra(edgeMatrix, coordMatrix, initialNode, endNode, nNodes)

# }