group8lab3/R/dijkstra.R

In bayubeta/group8lab3: Euclidean and Dijkstra's Algorithm.

#' Dijkstra's Algorithm
#' 
#' Calculates the shortest path from the initial node to every other node in the graph.
#'
#' @param graph A \code{data.frame} with three variables (\code{v1}, \code{v2} and \code{w}).
#' @param init_node A numeric scalar.
#' @return A \code{vector} containing the shortest path to every other node from the starting node as a vector.
#' @references \url{https://en.wikipedia.org/wiki/Dijkstra\%27s_algorithm}
#' @export

dijkstra <- function(graph, init_node){
  stopifnot(is.data.frame(graph), length(names(graph))==3, names(graph)==c("v1","v2","w"), is.numeric(init_node), length(init_node)==1)
  
  Q = unique(graph$v1) # Create a vector containing the set of nodes
  
  stopifnot(init_node %in% graph$v1) # stops if init_node is not a node in graph
  
  distance = as.list(rep(Inf, length(Q))) # Create a distance list with Inf as the elements
  names(distance) = Q # Name every element of the distance list with its respective node
  distance[init_node] = 0 # Change the distance value of initial node to 0
  
  while (length(Q)!=0){
    u = as.numeric(names(which.min(unlist(distance[Q])))) # Pick a node from the list distance with minimum distance value that's in Q
    Q = Q[-which(Q==u)] # Remove the node u from Q
    
    neighbor = intersect(Q, graph[which(graph$v1==u), ][,2]) # Create a vector of nodes that neighbor u
    
    for (i in neighbor){
      alt <- distance[u] + graph[which(graph$v1==u & graph$v2==i), ][3] # Calculate the distance from init_node to i (neighboring nodes)
      
      if (alt < distance[i]){
        distance[i] = alt # Change the value in the distance list if it's smaller than the current value
      }
    }
  }
  
  names(distance) = NULL # Remove the list name
  return(unlist(distance)) # Return the vector of distance values
}