R/dijkstra.R

In rjkhan/RCourse-lab3: Lab 3

luid<- "samza595 and rabsh696"
name<- "saman zahid & rabnawaz jansher"

#' @title Dijkstra Algorithm
#' @name  dijkstra
#' @param wiki_graph Data Frame of Graph
#' @param init_node Numeric Scalar Input
#' @return return a vector with number represent with the shortest path between nodes with inital node in graph.
#' @description dijkstra algo to find the shortest path from inital node to all other node in input graph
#' @references \url{https://en.wikipedia.org/wiki/Dijkstra\%27s_algorithm}
#' @export
dijkstra<- function(wiki_graph, init_node)
{
  col_name<- c("v1","v2","w")
  nodes <- as.numeric(unlist(unique(wiki_graph[1]))) #find a nodes from data frame
  if( !is.data.frame(wiki_graph) || !(is.numeric(init_node)) ||
      length(init_node) != 1  ||  !(is.element(init_node,nodes)) ||
      !any((col_name %in% colnames(wiki_graph)))
      )
  {
    stop()
  }

  nodes_length <- length(nodes) #get nodes array length
  matrix_wiki_graph <- matrix(c(Inf), nrow = nodes_length, ncol = nodes_length ) # create a martix of rows and column on nodes length

  for(y in 1:length(wiki_graph[,1]))  # convert data frame to matrix
  {
    matrix_wiki_graph[wiki_graph[y,1],wiki_graph[y,2]]<- wiki_graph[y,3]  #setting a value in Martix with weight
  }

  unvisted_nodes <- rep(FALSE,nodes_length) #set unvisted nodes to false be default
  v_result <- rep(Inf, nodes_length)  #initlize output vector with INfinity

  v_result[which(nodes == init_node)] <- 0   # set a init mode distance
  iterator<- 1 #iterator variable for node counts


  while(iterator < nodes_length)
  {
    min <- Inf

     for(i in 1:length(nodes)) # get minimum distance node
    {
      if(unvisted_nodes[i] == FALSE &&   v_result[i] <=  min)
      {
        min = v_result[i]
        min_index = i;
      }
    }

    u <- min_index # set miniumu index
    unvisted_nodes[u]<- TRUE #change the status of unvisited node to visted by setting True

    for(y in 1:length(nodes)) #find the neighbouring Nodes
    {
      if (!unvisted_nodes[y] && matrix_wiki_graph[u,y] &&
          v_result[u] != Inf && ( (v_result[u]+ matrix_wiki_graph[u,y] < v_result[y] )) )
      {
        v_result[y] = v_result[u] + matrix_wiki_graph[u,y];
      }
    }

    iterator <- iterator + 1

  }#end of whiel loop

  v_result
  return (c(v_result))
}


#' @title wiki_graph
#' @name  wiki_graph
#' @description wiki_graph
#' \itemize{
#'   \item v1 numeric vector
#'   \item v2 numeric vector
#'   \item w numeric vector
#' }
#' @references \url{https://en.wikipedia.org/wiki/Graph}
## wiki_graph
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))