R/dijkstra.R

In obiii/Lab3: Lab 3

#' Dijkstra Algorithm
#' Returns the shortest path from initial vertex to other vertexes
#' @param graph A \code{data.frame} which consist of 3 vectors named \code{v1}, \code{v1} and \code{w} and all must have the same length as shown in the example. \code{v1} and \code{v2} represent one edge in the graph, while \code{w} holds the distance. Edges must be included twice, from \code{v1} to \code{v2} and the other way round.
#' @param init_node A scalar stating from which vertexes the distances are to be calculated.
#'
#' @return Returns a vector consisting of the shortest paths from the node of origin \code{init_node} to the rest of the vertexes.
#'
#' @references https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#' 
#' @examples
#' dijkstra(wiki_graph, 1)
#' dijkstra(wiki_graph, 3)
#' 
#' @export
dijkstra = function(graph, init_node) {
  
  # Input validation
  if (!is.data.frame(graph) || length(graph) != 3) stop()
  if (!is.numeric(init_node)) stop()
  if (length(setdiff(names(graph),  c('v1', 'v2', 'w'))) > 1) stop()
  if (!init_node %in% graph$v1) stop()
  
  # Creating DF to store metadata for vertexes (ie. vertex number, visit status and distance from init_node
  vertexes = data.frame(unique(graph[1]),
                     rep(FALSE, times = length(graph[1])),
                     rep(Inf, times = length(graph[1])))
  names(vertexes) = c("Edge", "Visited", "Distance")
  
  # Setting the cost of init_node to 0
  vertexes[vertexes$Edge == init_node, 3] = 0
  # Setting current_vert to init_node
  current_vert = init_node
  
  while (nrow(vertexes[!vertexes$Visited,]) > 0) {
    
    # Iterate all vertexes and calculate distance
    for (i in 1:nrow(graph)) {
      if (graph[i, 1] == current_vert && !vertexes[vertexes$Edge == graph[i, 2], 2]) {
        tentative.distance = graph[i, 3] + vertexes[vertexes$Edge == current_vert, 3]
        if (tentative.distance < vertexes[vertexes$Edge == graph[i, 2], 3]) {
          vertexes[vertexes$Edge == graph[i, 2], 3] = tentative.distance
        }
      }
    }
    
    # Setting the current_vert to Visited
    vertexes[vertexes$Edge == current_vert, 2] = TRUE
    
    # Stop if destination is visited already
    unvisited.vertexes = vertexes[vertexes$Visited == FALSE,]
    # Also, checking if returns more than 1 vertex
    if (length(unvisited.vertexes[, 3]) != 0) {
      current_vert = unvisited.vertexes[unvisited.vertexes[[3]] == min(unvisited.vertexes[, 3]), 1]
      if (length(current_vert) > 1) {
        current_vert = current_vert[1] 
      }
    }
  }
  # Returning the results
  return(vertexes$Distance)
}