R/dijkstra.R

In zahrajalilpour292/first_package: It calculates the greatest common divisor of two numbers

#'Dijkstra Function
#'@export
#'
#'@name Dijkstra
#'
#'@description  This is greedy algorithm, which finds the shortest path in graph from the given node.
#'
#'@param graph is a data frame with 3 columns , v1 ,v2 and w
#'@param init_node is a atomic numeric value, which reprent the node in the graph
#'
#'@return It returns the numeric vector of shortest path from given node to all other nodes.
#'
#'@references "https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm"
#'
dijkstra <- function (graph, init_node){
  
  stopifnot(is.data.frame(graph))
  stopifnot(ncol(graph) == 3)
  stopifnot(colnames(graph)[1] == "v1",
            colnames(graph)[2] == "v2",
            colnames(graph)[3] == "w")
  stopifnot(init_node %in% unlist(graph["v1"]))
  #stopifnot(any(init_node == unlist(graph["v1"])))
  
  
  v1 <- graph$v1
  v2 <- graph$v2
  w <- graph$w
  unique_v1 <- unique(v1)
  unique_v2<- sort(unique(v2))
  # create a matrix and put related weight 
  new_mat <- matrix(Inf, nrow=length(unique_v1), ncol= length(unique_v2))
  for (i in seq_along(v1)){
    m <- v1[i]
    n <- v2[i]
    new_mat[m ,n] <- w[i]
    new_mat[m,m] <- 0
  }
  # initialize path and nodes by inf and false
  # step1: assign 0 to start point and infinity to all other paths
  total_distance <- rep (Inf, length(unique_v1))
  total_distance[init_node] <- 0
  # create a vector and put all node as unvisited, FALSE
  unvisited_vertics <- rep(FALSE, length(unique_v2))
  unvisited_vertics[init_node] <- TRUE
  repeat{
    for (i in seq_along(unique_v1)){
      for ( j in seq_along(unique_v2)){
        min_dist <- total_distance[i]+ new_mat[i,j]
        if(i!=j && min_dist < total_distance[j]){
          unvisited_vertics[j] <- TRUE
          total_distance[j] <- min_dist
        }
      }
    }
    if ((all(unvisited_vertics==TRUE))==TRUE){
      return(total_distance)
      break
    }
  }
}  

# 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,19))
# 
# dijkstra(wiki_graph, 3)