Dijkstra’s shortest pathway algorithm

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

One thought on “Dijkstra’s shortest pathway algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s