I’ve been playing around a lot with shortest pathways. Any code I have found has been for java or C/C++, with almost nothing in R other than the inbuilt functions in the packages igraph or gdistance. Yet this is actually relatively simple to compute.

Dijkstra’s algorithm has been of particular interest because both easy to implement and widely used. For a nice little animation on how it works, click here. Or you could just watch the video below.

So here is a simplified and commented R code from here for Dijkstra’s shortest pathway algorithm. Check out the original code, it’s pretty neat. It has a function which allows you to create S the distance matrix.

### Create a distance matrix S. ### Set all the impossible connections between nodes to a large number. ### Because the algorithm is looking for a minimum, very large distances will never be selected S=matrix(999,7,7) S[1,2]=1 S[1,3]=2 S[2,5]=2 S[3,4]=1 S[4,5]=1 S[4,6]=3 S[5,6]=2 S[6,7]=1 ### List of input parameters for function n=length(S[,1]) #number of nodes v=1 #source node dest=n #destination node cost=S #distance matrix ### Dijkstra's algorithm dijkstra=function(n,v,cost,dest){ #create empty variables to store data dest = numeric(n) flag = numeric(n) prev = numeric(n) # for every node in the network for(i in 1:n){ prev[i] = -1 dest[i] = cost[v,i] #= distance from start node v to every other node i in the network } #initialise counter which keeps track of number of steps through network count=2 # until we have reached our destination node n while(count <= n){ min=999 # loop over each node for(w in 1:n){ #if the new path is less long than the existing smallest one and flag[w] is equal to zero (aka we've not already incuded that node in route) if(dest[w] < min && !flag[w]){ # overwrite the minimum with the new shortest path and update counter min=dest[w] u=w } } flag[u] = 1 #indicate that we go to this site count = count+1 # loop over each node again keeping in mind where we have already been for(w in 1:n){ #if the new route is shorter than the previous route if((dest[u]+cost[u,w] < dest[w]) && !flag[w]){ dest[w]=dest[u]+cost[u,w] #update the distance to destination prev[w]=u #keep track of the node visited } } } return(prev) } ### create function which returns path savepath = function(f,x){ path=x while(f[x] != -1){ path=c(path,f[x]) x=f[x] savepath(f,x) } path=c(path,1) return(path) } ### Run Dijkstra's algorithm with our distance matrix prev = dijkstra(n,v,cost,dest) path = savepath(prev,dest) ### Print path path

Advertisements

[…] There’s also an example here showing how to write the algorithm from scratch in R: https://uqkdhanj.wordpress.com/2015/02/10/dijkstras-shortest-pathway-algorithm/ […]