CODEWITHSUNDEEP
rigraphdijkstra
user2014
user2014

Reputation: 69

How do I program this Dijkstra shortest distance algorithm in R?

Here is my Dijkstra data matrix. Note: distances between two nodes i and j that are not directly linked have been set to NA.

     node X1 X2 X3 X4 X5 X6
[1,]    1  0  3  7  4 NA NA
[2,]    2  3  0  2 NA NA  9
[3,]    3  7  2  0  1  3  6
[4,]    4  4 NA  1  0  3 NA
[5,]    5 NA NA  3  3  0  3
[6,]    6 NA  9  6 NA  3  0

I need to write a code that provide the shortest distance from Node 1 to Node N (so only a single number output is required, not the shortest path). The program should also work on a csv-file holding a symmetrical square direct-distance matrix of any dimensions, with any number of nodes numbered 1···N, and any positive distance values in the matrix. (Your program will be tested on such matrix.) The program should output the shortest distance from Node 1 to Node N.

I tried: Creating Temporary Matrix L(0)

l0data<-c(1,MatrixData[[1,1]],"Temp",2,MatrixData[[1,2]],"Temp",3,MatrixData[[1,3]],"Temp",4 ,MatrixData[[1,4]],"Temp",5, MatrixData[[1,5]],"Temp",6, MatrixData[[1,6]],"Temp")
l0<-matrix(l0data,nrow = 3, ncol = 6)
temp0<-l0[3,]=="Temp"

Select values & Node of L(0) to make permanent

l0SelectVal<-l0[2,temp0]
#select nodes of temporary l0
l0SelectNod<-l0[1,temp0]

Answers mininimum value of L(0)

L0<-which.min(l0SelectVal)
L0#value not used = step in between
L0Nod<-l0SelectNod[L0]
L0Val<-l0SelectVal[which.min(l0SelectVal)]

Then I repeated this for 6x times for L(1),...L(5) and:

Output shortest distance Matrix

AllData<-c("Node","Distance",L0Nod,L0Val,L1Nod,L1Val,L2Nod,L2Val,L3Nod,L3Val,L4Nod,L4Val,L5Nod,L5Val)
outputdata<-matrix(AllData,nrow = 2, ncol = 7)
outputdata[,c(4,5)]<-outputdata[,c(5,4)]

But obviously this is not the smartest way. So, help please: How do I write this code more efficiently?

Upvotes: 1

Views: 11734

Answers (1)

user20650
user20650

Reputation: 25874

Upgrade comment - I think you could use the functions in the igraph package for this

library(igraph)

# your data
mat <- as.matrix(read.table(text=
"node X1 X2 X3 X4 X5 X6
   1  0  3  7  4 NA NA
    2  3  0  2 NA NA  9
    3  7  2  0  1  3  6
    4  4 NA  1  0  3 NA
    5 NA NA  3  3  0  3
    6 NA  9  6 NA  3  0", header=T))

# prepare data for graph functions - set NA to zero to indicate no direct edge
nms <- mat[,1]
mat <- mat[, -1]
colnames(mat) <- rownames(mat) <- nms
mat[is.na(mat)] <- 0


# create graph from adjacency matrix
g <- graph.adjacency(mat, weighted=TRUE)
#plot(g)

# Get all path distances
(s.paths <- shortest.paths(g, algorithm = "dijkstra"))
#   1 2 3 4 5  6
#1  0 3 5 4 7 10
#2  3 0 2 3 5  8
#3  5 2 0 1 3  6
#4  4 3 1 0 3  6
#5  7 5 3 3 0  3
#6 10 8 6 6 3  0

Upvotes: 9

Related Questions