R/dijkistra.R

In rebinhosini/AdvancedR: Lab3

#' Dijkistra Algorithm
#' 
#' @description 
#' Algorithm to find the shortest path from inital node to all the other nodes.
#' Takes two inputs two find the shortest path from the initial node
#' 
#' @param graph is a datafram
#' @param init is the initial node
#' @return Shortest path from Initial Node
#' 
#' @export
dijkstra <- function(graph, init){  
  # Initial setup  
  init_node <- init   
  unique_nodes <- unique(graph[,"v1"])

  init_matrix <- matrix(Inf,
                        nrow = nrow(unique(graph["v1"])),
                        ncol = nrow(unique(graph["v1"])))
  
  for(i in 1:nrow(graph["v1"])){
    init_matrix[graph["v2"][i,],graph["v1"][i,]] <- graph["w"][i,]
  }
  
  # Creating the dist vectors
  dist <- rep(Inf,times = length(unique_nodes))

  dist[init_node] <- 0
  
  while(length(unique_nodes) != 0){
    idx <- which.min(dist[unique_nodes])
    u <- unique_nodes[idx]
    
    for(neighbour in unique_nodes){
      alt <- dist[u] + init_matrix[u,neighbour]
      if(alt < dist[neighbour]){
        dist[neighbour] <- alt
      } 
    }
    unique_nodes <- unique_nodes[-idx]
  }
  #not_found <- which(is.infinite(dist))
  #dist[not_found] <- dist[(not_found-1)]
  return(dist)
}