R/dijkstra.R

In harjew/lab3G3: Assigmnent 3

#' Dijkstra Algorithm
#'
#' Calculate the distece from the init node to all the other nodes.
#' 
#' @param graph Is a data frame with 3 variables, the first two is the nodes, the third is the distence.
#' @param init_note Is a numeric value of the node in questing.
#' 
#' @references https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#' 
#' @return The shortest distence from the \code{init_node} to all the nodes in \code{graph}.
#' 
#' @examples 
#' dijkstra(wiki_graph,1)
#' dijkstra(wiki_graph,3)
#' 
#' @export


dijkstra<-function(graph,init_note){
  # Validation
  if((is.data.frame(graph)==FALSE)){
    stop("'graph' is not a data.frame.")
  }else if(length(graph) != 3){
    stop("The data.frame must have 3 variables.")
  }else if(is.numeric(init_note)==FALSE){
    stop("'init_note' ist not numeric.")
  }else if(init_note%in%graph[,1] == FALSE & init_note%in%graph[,2] ==FALSE){
    stop("'init_note' is not included in the first variable.")
  }else if(all(names(graph)!=c("v1","v2","w"))){
    stop("Wrong names in the data frame")
  }
  for(i in 1:3){
    if(is.numeric(graph[,i]) == FALSE){
      stop("All the variables in 'graph' is not numeric.")
    }
  }

  node<-unique(graph[,1])
  # A check list of whitch node the loop have calculated.
  false_true<-rep(FALSE,length(node))
  # According to the theory of the algorithm, assign all the node a tentative distance
  # value, set the initial node to zero and the rest of the node to infinity.
  dist_node<-rep(Inf, length(node))

  nodes_saved<-data.frame(node,false_true,dist_node)

  # Save the first node.
  node_now <-init_note
  nodes_saved[nodes_saved$node == node_now,3]=0
  while(nrow(nodes_saved[!nodes_saved$false_true,])>0){
    for (i in 1:length(graph[,1])){
      # check if the node in qestion is the node we are calculate the distence from and saving the distence.
      # And if the node have a path to de next node.
      if((graph[i,1] == node_now) && !(nodes_saved[nodes_saved$node == graph[i,2],2])){
        dist<-graph[i,3]+nodes_saved[nodes_saved$node == node_now,3]
        if(dist < nodes_saved[nodes_saved$node == graph[i,2],3]){
          nodes_saved[nodes_saved$node == graph[i,2],3]<-dist
        }
      }
    }
    # now the switch of the node and save the value TRUE as a marker as its calculated.
    nodes_saved[nodes_saved$node==node_now,2]<-TRUE
    not_seen_node<-nodes_saved[nodes_saved$false_true == FALSE,]

    if(length(not_seen_node[,3]) != 0 ){
      node_now <- not_seen_node[not_seen_node[[3]] == min(not_seen_node[,3]),1]
      if(length(node_now) >1){
        node_now<-node_now[1]
      }
    }
  }
  # The function returns the last vector in the data frame nodes_saved.
  return(nodes_saved$dist_node)
}