R/dijkstra.r

In dimitramuni/euclidijk: Highest Common Factor And Finds Shortest Path

#'@title  Dijkstra
#'
#'@description  Dijkstra algorithm finds the shortest path for a given graph from a input node.
#'
#'@param df Data.Frame
#'@param n numeric_variable
#'
#'
#'@return vector shortest path vector \code{df} from source node \code{n}
#'
#'@examples
#'wiki_graph <-data.frame(v1=c(1,1,1,2,2,2,3,3,3,3,4,4,4,5,5,6,6,6),
#'v2=c(2,3,6,1,3,4,1,2,4,6,2,3,5,4,6,1,3,5),
#'w=c(7,9,14,7,10,15,9,10,11,2,15,11,6,6,9,14,2,9))
#'dijkstra(wiki_graph, 1)
#'
#'\dontrun{dijkstra(1:100,5)}
#'\dontrun{dijkstra(1:100,"A")}
#'
#'@references https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#'@aliases dijkstra shortest-path
#'@export


dijkstra<-function(df,n){


            Q=unique(df[,1])            # create vertex set Q


            stopifnot(n%in%Q & is.data.frame(df))           # check if node n is in vector Q


            dist<-rep(Inf,length(Q))    # setting all the distances to Inf
            prev<-rep(NA,length(Q))

            dist[which(Q==n)]<-0


            while (length(Q)!=0)
            {
              u<-which(dist==min(dist[Q])) #find which vertex is the nearest to source node
              Q<-Q[-which(Q==u)]
              # print(u);print(Q)



                for (v in Q){

                  wa<-df[which(df$v1==u),]
                  if(any(wa$v2==v)){
                    # a<-df[df$v1==u & df$v2==v,3]

                                    alt<-dist[u]+df[df$v1==u & df$v2==v,3]
                                    if(alt<dist[v])
                                     {
                                       dist[v]<-alt
                                       prev[v]<-u

                                     }

                                     }
                              }


              }
              return(dist)

                                }