dijkstra: Shortest path through network using dijkstra's algorithm

In locationgamer: Identification of Location Game Equilibria in Networks

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

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)

locationgamer documentation built on Dec. 18, 2020, 5:08 p.m.