Dijkstra's Shortest Path Algorithm

Dijkstra’s shortest path algorithm is used to efficiently determine the shortest path between a starting node and an ending node in a graph, where each edge has a non-negative weight or cost associated with it. This algorithm is particularly useful in scenarios where you need to find the most efficient or cost-effective route, such as in transportation networks, communication networks, or any other systems that can be represented as a weighted graph.

Dijkstra’s algorithm is a greedy algorithm that works by iteratively selecting the unvisited node with the smallest known distance from the source node and updating the distances of its neighboring nodes accordingly. It keeps track of the nodes that have been visited and the current shortest path to each node, and it continues to explore the graph until it reaches the destination node.

Weighted Graphs and Shortest Path Problem

A weighted graph is a type of graph where each edge (the connection between two nodes) has an associated numerical value, called a weight. This weight can represent various properties, such as the distance, cost, or time required to travel between the connected nodes.

Here’s an example of a weighted graph represented using ASCII art:

   5
A ---- B
| \    |
|  \   |
3   8  1
|    \ |
|     \|
C ---- D
   2

In this example, the graph consists of four nodes (A, B, C, and D) and five edges. The numbers associated with each edge represent the weight or cost of traveling between the connected nodes. For example, the edge A->B has weight 5, edge A->D has weight 8 and so on. If you need to travel from A to D, you can decide on the shortest distance by computing weights of all shortest paths: A->B->D has a total weight of 6, A->D has a total weight of 8, A->C->D has a total weight of 5. So choosing the last path is more efficient.

The above graph can be represented as an adjacency list shown below:

graph = {
  "A" : [("B", 5), ("C", 3), ("D", 8)],
  "B" : [("D", 1)],
  "C" : [("D", 2)],
  "D" : []
}

Dijkstra’s Algorithm to find shortest distance

Dijkstra’s Algorithm uses a priority queue to always process the node with the smallest known distance from the start node. As it explores the graph, it updates the distances to each node if a shorter path is found. The algorithm continues until it reaches the end node or exhausts all possible paths. By always processing the closest unvisited node first, it ensures that when it reaches the end node, the path to it is with the shortest distance possible. Below is the implementation:


from heapq import heappop, heappush

def find_shortest_distance(graph, start_node, end_node):
  """
  Find the shortest distance between start_node and end_node
  in a weighted graph using Dijkstra's algorithm.

  Args:
  graph (dict): A dictionary representing the graph. Each key is a node, 
  and the value list containing tuples of neighboring nodes and weights
  start_node: The starting node for the path.
  end_node: The destination node for the path.

  Returns:
  int: The shortest distance from start_node to end_node.
  Returns -1 if no path exists.
  """
  
  # distances dictionary is used to store the smallest
  # distance from start node to each node in the graph
  # Initialize distances with infinity for all nodes
  distances = {node: float('inf') for node in graph}
  # Set the distance to the start node from itself to 0
  distances[start_node] = 0
  
  # Initialize priority queue with start node
  # Priority queue entries are tuples of (distance, node)
  priority_queue = [(0, start_node)]
  
  while priority_queue:
    # Get the node with the smallest distance from the priority queue
    current_distance, current_node = heappop(priority_queue)
    
    # If we've reached the end node, we're done
    if current_node == end_node:
      return current_distance
    
    # If we've found a longer path to the current node, skip it
    if current_distance > distances[current_node]:
      continue
    
    # Explore neighbors of the current node
    for neighbor, weight in graph[current_node]:
      # Calculate tentative distance to the neighbor
      distance = current_distance + weight
      
      # If we've found a shorter path to the neighbor, update it
      if distance < distances[neighbor]:
        distances[neighbor] = distance
        # Add the neighbor to the priority queue
        heappush(priority_queue, (distance, neighbor))
  
  # If we've exhausted all possible paths without reaching the end node,
  # there's no path from start to end
  return -1


graph = {
  "A" : [("B", 5), ("C", 3), ("D", 8)],
  "B" : [("D", 1)],
  "C" : [("D", 2)],
  "D" : []
}

print("Shortest distance between 'A' and 'D' is:")
print(find_shortest_distance(graph, "A", "D")) # 5 (A->C->D)


#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

int find_shortest_distance(unordered_map<string, vector<pair<string, int>>>& graph, string start_node, string end_node) {
  // distances dictionary is used to store the smallest
  // distance from start node to each node in the graph
  // Initialize distances with infinity for all nodes
  unordered_map<string, int> distances;
  for (auto& [node, neighbors] : graph) {
    distances[node] = INT_MAX;
  }
  // Set the distance to the start node from itself to 0
  distances[start_node] = 0;

  // Initialize priority queue with start node
  // Priority queue entries are tuples of (distance, node)
  priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> priority_queue;
  priority_queue.push({0, start_node});

  while (!priority_queue.empty()) {
    // Get the node with the smallest distance from the priority queue
    int current_distance = priority_queue.top().first;
    string current_node = priority_queue.top().second;
    priority_queue.pop();

    // If we've reached the end node, we're done
    if (current_node == end_node) {
      return current_distance;
    }

    // If we've found a longer path to the current node, skip it
    if (current_distance > distances[current_node]) {
      continue;
    }

    // Explore neighbors of the current node
    for (auto& [neighbor, weight] : graph[current_node]) {
      // Calculate tentative distance to the neighbor
      int distance = current_distance + weight;

      // If we've found a shorter path to the neighbor, update it
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        // Add the neighbor to the priority queue
        priority_queue.push({distance, neighbor});
      }
    }
  }

  // If we've exhausted all possible paths without reaching the end node,
  // there's no path from start to end
  return -1;
}

int main() {
  unordered_map<string, vector<pair<string, int>>> graph = {
    {"A", {{"B", 5}, {"C", 3}, {"D", 8}}},
    {"B", {{"D", 1}}},
    {"C", {{"D", 2}}},
    {"D", {}}
  };

  cout << "Shortest distance between 'A' and 'D' is:" << endl;
  cout << find_shortest_distance(graph, "A", "D") << endl; // 5 (A->C->D)

  return 0;
}


import java.util.*;

public class Main {
  public static int findShortestDistance(Map<String, List<Edge>> graph, String startNode, String endNode) {
    // distances map is used to store the smallest
    // distance from start node to each node in the graph
    // Initialize distances with infinity for all nodes
    Map<String, Integer> distances = new HashMap<>();
    for (String node : graph.keySet()) {
      distances.put(node, Integer.MAX_VALUE);
    }
    // Set the distance to the start node from itself to 0
    distances.put(startNode, 0);

    // Initialize priority queue with start node
    // Priority queue entries are tuples of (distance, node)
    PriorityQueue<Pair<Integer, String>> priorityQueue = new PriorityQueue<>((a, b) -> a.getKey() - b.getKey());
    priorityQueue.offer(new Pair<>(0, startNode));

    while (!priorityQueue.isEmpty()) {
      // Get the node with the smallest distance from the priority queue
      int currentDistance = priorityQueue.peek().getKey();
      String currentNode = priorityQueue.poll().getValue();

      // If we've reached the end node, we're done
      if (currentNode.equals(endNode)) {
        return currentDistance;
      }

      // If we've found a longer path to the current node, skip it
      if (currentDistance > distances.get(currentNode)) {
        continue;
      }

      // Explore neighbors of the current node
      for (Edge neighbor : graph.get(currentNode)) {
        // Calculate tentative distance to the neighbor
        int distance = currentDistance + neighbor.weight;

        // If we've found a shorter path to the neighbor, update it
        if (distance < distances.get(neighbor.node)) {
          distances.put(neighbor.node, distance);
          // Add the neighbor to the priority queue
          priorityQueue.offer(new Pair<>(distance, neighbor.node));
        }
      }
    }

    // If we've exhausted all possible paths without reaching the end node,
    // there's no path from start to end
    return -1;
  }

  public static void main(String[] args) {
    // Graph representation
    Map<String, List<Edge>> graph = new HashMap<>();
    graph.put("A", Arrays.asList(new Edge("B", 5), new Edge("C", 3), new Edge("D", 8)));
    graph.put("B", Arrays.asList(new Edge("D", 1)));
    graph.put("C", Arrays.asList(new Edge("D", 2)));
    graph.put("D", new ArrayList<>());

    System.out.println("Shortest distance between 'A' and 'D' is:");
    System.out.println(findShortestDistance(graph, "A", "D")); // 5 (A->C->D)
  }

  static class Edge {
    String node;
    int weight;

    Edge(String node, int weight) {
      this.node = node;
      this.weight = weight;
    }
  }

  static class Pair<K, V> {
    private K key;
    private V value;

    Pair(K key, V value) {
      this.key = key;
      this.value = value;
    }

    K getKey() {
      return key;
    }

    V getValue() {
      return value;
    }
  }
}

The above code computes the shortest distance between a given start node and end node. Once the end node is reached, processing of all other nodes is stopped and the shortest distance is returned. If you wish to compute shortest distance to all nodes from the start node, you can remove the check: if current_node == end_node and continue until all the nodes in the priority queue are processed. After this the distances dictionary contains the shortest distance from the start node to all other nodes in the graph.

Dijkstra’s Algorithm to find shortest path

In addition to the distances details stored in the previous algorithm, we also need to store the parent/predecessor node for each node along the shortest path. Once the end node is reached, we can construct the shortest path using the predecessor data for each node. Below is the implementation:


from heapq import heappop, heappush

def find_shortest_path(graph, start_node, end_node):
  """
  Find the shortest path between start_node and end_node
  in a weighted graph using Dijkstra's algorithm.

  Args:
  graph (dict): A dictionary representing the graph. Each key is a node, 
  and the value is a list containing tuples of neighboring nodes and weights
  start_node: The starting node for the path.
  end_node: The destination node for the path.

  Returns:
  list of nodes along the shortest path
  """
  
  # Initialize distances with infinity for all nodes
  # Set the distance to the start node from itself to 0
  distances = {node: float('inf') for node in graph}
  distances[start_node] = 0
  
  # Initialize predecessors with None for all nodes
  predecessors = {node: None for node in graph}
  
  # Initialize priority queue with start node
  priority_queue = [(0, start_node)]
  
  while priority_queue:
    # Get the node with the smallest distance from the priority queue
    current_distance, current_node = heappop(priority_queue)
    
    # If we've reached the end node, construct and return the path
    if current_node == end_node:
      path = []
      while current_node:
        path.append(current_node)
        current_node = predecessors[current_node]
      return (current_distance, list(reversed(path)))
    
    # If we've found a longer path to the current node, skip it
    if current_distance > distances[current_node]:
      continue
    
    # Explore neighbors of the current node
    for neighbor, weight in graph[current_node]:
      # Calculate tentative distance to the neighbor
      distance = current_distance + weight
      
      # If we've found a shorter path to the neighbor, update it
      if distance < distances[neighbor]:
        distances[neighbor] = distance
        predecessors[neighbor] = current_node
        heappush(priority_queue, (distance, neighbor))
  
  # If we've exhausted all possible paths without reaching the end node,
  # there's no path from start to end
  return (-1, [])

# Example usage
graph = {
  "A" : [("B", 5), ("C", 3), ("D", 8)],
  "B" : [("D", 1)],
  "C" : [("D", 2)],
  "D" : []
}


(shortest_distance, path) = find_shortest_path(graph, "A", "D")
print(f"Shortest path between 'A' and 'D' is {shortest_distance} along below path:")
print(' -> '.join(path)) # A -> C -> D


#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>

using namespace std;

// Function to find the shortest path between start_node and end_node
// in a weighted graph using Dijkstra's algorithm
pair<int, vector<string>> find_shortest_path(unordered_map<string, vector<pair<string, int>>>& graph, string start_node, string end_node) {
  // Distances dictionary is used to store the smallest
  // distance from start node to each node in the graph
  // Initialize distances with infinity for all nodes
  unordered_map<string, int> distances;
  for (auto& [node, _] : graph) {
    distances[node] = INT_MAX;
  }
  // Set the distance to the start node from itself to 0
  distances[start_node] = 0;

  // Predecessors dictionary stores the previous node in the shortest path
  // Initialize with None for all nodes
  unordered_map<string, string> predecessors;
  for (auto& [node, _] : graph) {
    predecessors[node] = "";
  }

  // Initialize priority queue with start node
  // Priority queue entries are pairs of (distance, node)
  priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> priority_queue;
  priority_queue.push({0, start_node});

  while (!priority_queue.empty()) {
    // Get the node with the smallest distance from the priority queue
    int current_distance = priority_queue.top().first;
    string current_node = priority_queue.top().second;
    priority_queue.pop();

    // If we've reached the end node, construct and return the path
    if (current_node == end_node) {
      vector<string> path;
      while (!current_node.empty()) {
        path.push_back(current_node);
        current_node = predecessors[current_node];
      }
      reverse(path.begin(), path.end());
      return {current_distance, path};
    }

    // If we've found a longer path to the current node, skip it
    if (current_distance > distances[current_node]) {
      continue;
    }

    // Explore neighbors of the current node
    for (auto& [neighbor, weight] : graph[current_node]) {
      // Calculate tentative distance to the neighbor
      int distance = current_distance + weight;

      // If we've found a shorter path to the neighbor, update it
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        // Update the predecessor along shortest path for this neighbor
        predecessors[neighbor] = current_node;
        // Add the neighbor to the priority queue
        priority_queue.push({distance, neighbor});
      }
    }
  }

  // If we've exhausted all possible paths without reaching the end node,
  // there's no path from start to end
  return {-1, {}};
}

int main() {
  // Example usage
  unordered_map<string, vector<pair<string, int>>> graph = {
    {"A", {{"B", 5}, {"C", 3}, {"D", 8}}},
    {"B", {{"D", 1}}},
    {"C", {{"D", 2}}},
    {"D", {}}
  };

  auto [shortest_distance, path] = find_shortest_path(graph, "A", "D");
  cout << "Shortest path between 'A' and 'D' is " << shortest_distance << " along below path:" << endl;
  for (const auto& node : path) {
    cout << node << " -> ";
  }
  cout << "D" << endl;

  return 0;
}


import java.util.*;

public class Main {
  public static Pair<Integer, List<String>> findShortestPath(Map<String, List<Pair<String, Integer>>> graph, String startNode, String endNode) {
    // distances map is used to store the smallest
    // distance from start node to each node in the graph
    // Initialize distances with infinity for all nodes
    Map<String, Integer> distances = new HashMap<>();
    for (String node : graph.keySet()) {
      distances.put(node, Integer.MAX_VALUE);
    }
    // Set the distance to the start node from itself to 0
    distances.put(startNode, 0);

    // predecessors map stores the previous node in the shortest path
    // Initialize with null for all nodes
    Map<String, String> predecessors = new HashMap<>();
    for (String node : graph.keySet()) {
      predecessors.put(node, null);
    }

    // Initialize priority queue with start node
    // Priority queue entries are pairs of (distance, node)
    PriorityQueue<Pair<Integer, String>> priorityQueue = new PriorityQueue<>((a, b) -> a.getKey() - b.getKey());
    priorityQueue.offer(new Pair<>(0, startNode));

    while (!priorityQueue.isEmpty()) {
      // Get the node with the smallest distance from the priority queue
      Pair<Integer, String> currentEntry = priorityQueue.poll();
      int currentDistance = currentEntry.getKey();
      String currentNode = currentEntry.getValue();

      // If we've reached the end node, construct and return the path
      if (currentNode.equals(endNode)) {
        List<String> path = new ArrayList<>();
        while (currentNode != null) {
          path.add(0, currentNode);
          currentNode = predecessors.get(currentNode);
        }
        return new Pair<>(currentDistance, path);
      }

      // If we've found a longer path to the current node, skip it
      if (currentDistance > distances.get(currentNode)) {
        continue;
      }

      // Explore neighbors of the current node
      for (Pair<String, Integer> neighbor : graph.get(currentNode)) {
        String neighborNode = neighbor.getKey();
        int weight = neighbor.getValue();
        // Calculate tentative distance to the neighbor
        int distance = currentDistance + weight;

        // If we've found a shorter path to the neighbor, update it
        if (distance < distances.get(neighborNode)) {
          distances.put(neighborNode, distance);
          // Update the predecessor along shortest path for this neighbor
          predecessors.put(neighborNode, currentNode);
          // Add the neighbor to the priority queue
          priorityQueue.offer(new Pair<>(distance, neighborNode));
        }
      }
    }

    // If we've exhausted all possible paths without reaching the end node,
    // there's no path from start to end
    return new Pair<>(-1, new ArrayList<>());
  }

  public static void main(String[] args) {
    // Example usage
    Map<String, List<Pair<String, Integer>>> graph = new HashMap<>();
    graph.put("A", new ArrayList<>(Arrays.asList(new Pair<>("B", 5), new Pair<>("C", 3), new Pair<>("D", 8))));
    graph.put("B", new ArrayList<>(Arrays.asList(new Pair<>("D", 1))));
    graph.put("C", new ArrayList<>(Arrays.asList(new Pair<>("D", 2))));
    graph.put("D", new ArrayList<>());

    Pair<Integer, List<String>> result = findShortestPath(graph, "A", "D");
    int shortestDistance = result.getKey();
    List<String> path = result.getValue();

    System.out.println("Shortest path between 'A' and 'D' is " + shortestDistance + " along below path:");
    System.out.println(String.join(" -> ", path)); // A -> C -> D
  }
}

Similar to the distance finding algorithm, the above shortest path finding algorithm can also be modified to find shortest paths between start node and all other nodes in the graph.

TODO: Add time and space complexity analysis

Limitations and Considerations

One of the primary limitations of Dijkstra’s algorithm is its inability to handle negative edge weights. Dijkstra’s algorithm assumes that all edge weights are non-negative. If there are negative edge weights, the algorithm may not produce correct results. This is because Dijkstra’s algorithm greedily selects the next node based on the current shortest distance, which can lead to suboptimal paths if a later negative edge could have provided a shorter path.

In scenarios where the graph contains negative edge weights, other algorithms, such as the Bellman-Ford algorithm or the Floyd-Warshall algorithm, may be more suitable. These algorithms are designed to handle graphs with negative edge weights and can find the shortest paths even in the presence of negative cycles.

Also Dijkstra’s algorithm finds the shortest path from a single source to all other vertices. If shortest paths from multiple sources are required, the algorithm needs to be run separately for each source, which can be inefficient. In case like this, Floyd-Warshall algorithm might be more suitable.

Why doesn’t Dijkstra Algorithm work for Negative Weight Graphs?

Consider the graph illustrated below:

       A
      / \
     /   \
   (5)   (2)
   /       \
  /         \
 B---(-10)-->C

There are 3 edges in the graph: A->B with weight 5, A->C with weight 2 and B->C with weight -10. Let’s say we need to find out the shortest distance between node A and node C.

Below is what the Dijkstra algorithm would do:

Set the distance of node A from itself to 0
Pop node A from the priority queue and add it’s neighbors to the priority queue. The queue now contains node C with distance 2 and node B with distance 5.
Next pop the node with lowest weight, node C in this case
This node is what we are looking for, so the algorithm assumes this is the shortest path and returns A->C as shortest path with total weight as 2.
However the actual shortest path is A->B->C with a total weight of 5 + -10 = -5.

You can explore more about this in the discussions here and here.

If you try out the algorithm provided to find out minimum distance between node A and all other nodes in the graph, the algorithm would work as expected and we get the desired results: distances = {'A': 0, 'B': 5, 'C': -5}. However, the time complexity guarantee offered by Dijkstra’s algorithm for unweighted graphs is no longer applicable and it would be much higher than other algorithms. So doing this is not recommended.

You can learn more about different variations of Dijkstra’s algorithm here.