Dijkastra Algorithm for Shortest Path Problem (SPP) in R (Code to be tested and validated)

R Code for SPP algorithm

ShortestPathProblemDijkastra <- function(SPData) {

ArcData <- SPData

colnames(ArcData) <- c("fromNode","toNode","arcDist")

RawNodeList <- c(ArcData[,1],ArcData[,2])

RawNodeList <- unique(RawNodeList)

RawNodeList <- data.frame(RawNodeList)

PreNodes <- unique(c(ArcData[,2]))

PreNodes <- data.frame(PreNodes)

PostNodes <- unique(c(ArcData[,1]))

PostNodes <- data.frame(PostNodes)

library(dplyr)

colnames(PreNodes) <- c("Node")

colnames(PostNodes) <- c("Node")

colnames(RawNodeList) <- c("Node")

NoPreNodes <- anti_join(RawNodeList,PreNodes,by=c("Node"))

NoPostNodes <- anti_join(RawNodeList, PostNodes,by=c("Node"))

Startnode <- NoPreNodes[1]

Endnode <- NoPostNodes[1]

NodeLabel <- data.frame(matrix(NA,ncol = 4))

colnames(NodeLabel) <- c("fromNode","Dist","PreNode","Type")

NodeLabel[1,1] <- NoPreNodes[1]

NodeLabel[1,2] <- 0

NodeLabel[1,4] <- ("Permanent")

i <- 2

dist <- 0

NodeLabelMod <- data.frame(matrix(NodeLabel[1,1],nrow = 1,ncol = 1))

colnames(NodeLabelMod) <- ("fromNode") 

while (nrow(NodeLabel) < nrow(RawNodeList)) {

ds <- merge(NodeLabelMod,ArcData)

aa <- data.frame(ds$fromNode[ds$arcDist == min(ds$arcDist)],

ds$toNode[ds$arcDist == min(ds$arcDist)], ds$arcDist[ds$arcDist == 

min(ds$arcDist)])

NodeLabel[i,1] <- aa[1,2]

NodeLabel[i,2] <- NodeLabel[i-1,2] + aa[1,3]

NodeLabel[i,3] <- NoPreNodes[1]

NodeLabel[i,4] <- ("Permanent")

NodeLabelMod[1] <- NodeLabel[i,1]

NoPreNodes[1] <- NodeLabel[i,1]

dist <- dist + aa[1,3] 

i <- i + 1

}

rm(list=c("ArcData","RawNodeList","PreNodes","PostNodes",

"NoPreNodes","NoPostNodes","Startnode","Endnode","i","dist",

"ds","aa"))

NodeLabel <- NodeLabel[,-4] 

colnames(NodeLabel) <- c("Node","Dist","PreNode")

return(NodeLabel)

}

R Code for finding shortest path to a node based on preceding result (res) and node

NodeNetwork <- function(res,node) { 

seq <- NULL

n <- which(res$Node == as.character(node))

for (i in 1:n) {

aa <- res[i,1]

seq <- paste(seq,aa,sep="---->")

}

seq <- substring(seq,6)

MinDist <- res[n,2]

return(paste("The sequence for flow is: ",seq, " with distance of: 

",MinDist,sep=""))

}

Illustration:

ReadData <- read.csv("SPP_Data.csv")

SPP_Data.csv:

 
 


  
fromnode
  
tonode
  
arcdistance
 

  
1
  
2
  
5
 

  
1
  
3
  
1
 

  
2
  
4
  
7
 

  
2
  
5
  
1
 

  
2
  
6
  
6
 

  
3
  
2
  
2
 

  
3
  
4
  
6
 

  
3
  
5
  
7
 

  
4
  
3
  
7
 

  
4
  
6
  
4
 

  
4
  
7
  
6
 

  
5
  
4
  
3
 

  
5
  
6
  
5
 

  
5
  
7
  
9
 

  
6
  
2
  
7
 

  
6
  
7
  
2

res <- ShortestPathProblemDijkastra(ReadData)

NodeNetwork(res,7)


Result:



[1] "The sequence for flow is: 1---->3---->2---->5---->4---->6---->7 with 
distance of: 13"