This section deals with the analysis of all possible shortest paths for a given single source (that is-a start vertex V) in a graph G. The shortest paths are determined between the start vertex V and all other vertices in the graph. In other words, the computation of the shortest distance between a start vertex V and an end vertex W would involve finding all possible shortest paths from start vertex V to all other intermediate vertices (worst-case scenario). It is widely used in computer routing networks, which involve transfer of data from one start source to multiple sources across the network. The time taken to transfer data or the edge network connectivity governs the cost parameter of the graph network.

As studied earlier, graphs can be broadly classified based on direction and edge weights. In case of undirected and unweighted (or equal weighted) graphs, the BFS algorithm is widely used to estimate single-source shortest paths. Once the edges are assigned with different weights, Dijkstra's algorithm is widely used to estimate single-source shortest paths regardless of their directions. The key features of Dijkstra's algorithm are as follows:

Initially, an infinite value is assigned to each vertex of the graph. The value here represents the distance from the given source vertex. To begin with, the value of the source vertex is decreased to zero, and all its adjacent neighbors are processed with the updated distance values. Then, the vertex with the least value is extracted, and the values of all its adjacent unmarked vertices are updated accordingly. This process continues until all the vertices are extracted and all the values processed. In the end, the algorithm returns two key outputs. One output displays the shortest possible distances to each vertex from the source vertex V, while the second output shows the linkage of each vertex with its parent vertex. The second output is used to deduce the shortest path to any vertex from the given source vertex V.

In the current implementation of Dijkstra's algorithm, all the vertices and their distance values are initially stored in a priority queue. The priority queue is used for insertion (push) and extraction (extractMinVertex) of key-value pairs. The Push function is used in insertion of a new key-value pair to the priority queue, and the extractMinVertex function is used in extraction of a key-value pair with the least value. The value represents the distance of the key (vertex) from the source vertex. The vertices are subsequently extracted, processed, and stored in two different hash maps. One hash map stores the shortest distances from the source vertex, and the other stores parent vertices to keep track of the shortest path from the source vertex.

The current implementation of the priority queue function uses R5 classes. The R code is as follows:

PriorityQueueInit <-  
  setRefClass("PriorityQueueInit", 
  fields = list(keys = "integer", values = "integer"), 
  methods = list( 
   push = function(key,value) { 
     keys <<- append(keys, key) 
     values <<- append(values, value) 
   }, 
   extractMinVertex = function() { 
     minPos <- which(values==min(values)) 
     key <- keys[[minPos]] 
     value <- values[[minPos]] 
     return(list(key=key,value=value)) 
   } 
))

Using the preceding priority function and two hash maps (from the cran package hashmap), the following R code implements Dijkstra's algorithm. The four inputs to this function are Graph_ADT, a sourceVertex, a vector of all the vertices of the graph, and the number of vertices, n:

 DijkstraShortestPath <- function(graph,sourceVertex,vertices,n) { 
  library(hashmap)  ## To create new hashmap instance 
  ## Initiate a new priority queue 
  priorityQueue <- PriorityQueueInit$new() 
   
  # Initiate a hashmap to store shortest distance from  
  # source vertex to every vertex 
  distanceMap <- hashmap(keys=vertices, values = rep(0,n)) 
   
  # Initiate another hashmap to store the parent vertex to keep a    
  # track of shortest path from source vertex to every vertex 
  parentMap <- hashmap(keys = sourceVertex, values = "NULL") 
   
  # initialize priority queue with value of all vertices to infinity 
  for( i in vertices) priorityQueue$push(vertices[i],Inf) 
   
  ## Set the distance of sourceVertex as zero 
  priorityQueue$values[which(priorityQueue$keys==sourceVertex)] <- 0 
   
  ## Begin iteration till the all the vertices from  
  ## priorityQueue becomes empty 
  while(length(priorityQueue$keys) != 0){ 
  ## Extract vertex with minimum value from priority queue  
    headVertex <- priorityQueue$extractMinVertex() 
     
    ## Assign the key of the head vertex as current vertex 
    currentVertex <- headVertex$key 
     
    ## Append distancemap with current key and its value 
    distanceMap[[currentVertex]] <- headVertex$value 
     
    ## Check for all directly connected vertices for current vertex 
    for(conVert in getConVertex(graph,currentvertex)){ 
      ## get all the corresponding edge value 
      edgeValue <- getEdgeValue(graph,currentvertex,conVert) 
       
      ## Check priority queue contains the adjacent connected  
      ## vertex (conVert) or not 
      if(!priorityQueue$keys %in% conVert){ next } 
       
      ## Now evaluate the distance of the adjacent vertex (conVert) 
      updDistance <- distanceMap[[currentVertex]] + edgeValue 
 
      ## Updated parentmap using value of the adjacent vertex  
      ## in priorityQueue   
      if(priorityQueue$values[which(priorityQueue$keys==conVert)]  
      > updDistance){ 
        priorityQueue$values[which(priorityQueue$keys==conVert)] <-    
        updDistance 
        parentmap[[conVert]]  <- currentVertex 
      } 
    } 
  }  
}

The time complexity of the current implementation is θ(|E| log(V)), as during the worst case scenario, the size of the priority queue will be |V|, and the number of push and extract operations will be |E|. However, memory complexity of the current implementation is θ(|E| + |V|), because during the worst case scenario, the size of the priority queue and distance map will be |V|, and the size of the parent map will be |E|.

Let us understand the working of Dijkstra's algorithm based on the graph given in Figure 8.9. Initialize vertex A as the source vertex with value zero and rest of the vertices with value infinity. Then extract A, as it has the minimum value, and check for all its adjacent connected vertices. Update vertices B, C, E, and F with the respective distance values of edges (from source vertex A). Then, extract vertex C, as it has the least value among the remaining lot of vertices. Now, search for its connected vertices, which is F. The current value of F is 25, based on edge (A, F); however, based on the edge connection from C, the distance of F from A is the sum of edge distances (A, C) and (C, F), which comes out to be 19 (lesser than 25). Hence, update the value of F with 19, and assign C as a parent of F. Now, based on the updated vertex values, select the unmarked/unvisited vertex with the least distance, and continue updating the adjacent vertices. Table 8.10 shows the updated vertex values at the end of every extraction.

Table 8.10: Illustration of updated vertices values at the end of each extraction using Dijkstra's algorithm