Dijkstra's Shortest Path Algorithm Implementation

Dijkstra's algorithm is used to find the shortest paths from a source node to all other nodes in a directed or undirected weighted graph. Dijkstra's algorithm is a well-known algorithm for finding the shortest paths between nodes in a graph, particularly useful when dealing with graphs without negative edge weights.

Key Concepts

Dijkstra's Algorithm

• Purpose: To find the shortest path from a single source node to all other nodes in a graph.
• Limitations:
  • Not applicable to graphs with negative edge weights.
  • Cannot handle graphs containing negative cycles.
  • Does not provide information about unreachable nodes.

Graph Representation

• The graph is represented using an adjacency list, where each node is mapped to a list of its neighbors and the respective edge weights.

Code Breakdown

1. Class Definition: DirectedWeightedGraph

• Adjacency List: The graph is stored as an unordered_map where each node has a list of its neighboring nodes and the weights of the edges connecting them.
• Functions:
  • insertEdge: Adds an edge to the graph. It supports both directed and undirected graphs.
  • printAdjacencyList: Prints the adjacency list of the graph for debugging purposes.
  • dijkstrasShortestPath: Implements Dijkstra's algorithm to find the shortest path from a source node to all other nodes.

2. Function: insertEdge

• Parameters:
  • source: The starting node of the edge.
  • destination: The ending node of the edge.
  • weight: The weight of the edge.
  • isDirected: Boolean indicating whether the graph is directed or undirected.
• Functionality:
  • If the graph is directed, an edge is added from the source to the destination.
  • If the graph is undirected, edges are added in both directions.

3. Function: dijkstrasShortestPath

• Parameters:
  • source: The source node from which shortest paths are calculated.
  • numberOfNodes: Total number of nodes in the graph.
• Data Structures:
  • shortestDistances: A vector storing the shortest distance from the source to each node, initialized to INT_MAX to signify infinity.
  • nodesSet: A set that acts as a priority queue, storing pairs of node distances and node values, sorted by distance.
• Algorithm:
  • The source node is inserted into the set with a distance of 0.
  • The algorithm iterates over the set, picking the node with the smallest distance (similar to BFS).
  • For each node, it checks its neighbors and updates their shortest distances if a shorter path is found through the current node.
  • The updated neighbors are reinserted into the set for further processing.

4. Main Function

• Graph Construction: The graph is built by inserting edges with specified weights.
• Shortest Path Calculation: Dijkstra's algorithm is run from a specified source node.
• Output: The shortest distances from the source node to all other nodes are printed.

Example

#include <climits>
#include <iostream>
#include <list>
#include <ostream>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

// NOTE:
// -> this approach can be used on both directed and undirected graphs
// Limitations of Dijkstra's Algorithm:
//  - Inapplicable to graphs with negative edge weights.
//  - Unable to handle graphs containing negative cycles.
//  - Does not provide information about unreachable nodes.

// Class representing a directed weighted graph
class DirectedWeightedGraph {
public:
  // Adjacency List representation: <vertex value, <neighbor, weight>>
  unordered_map<int, list<pair<int, int>>> adjacencyList;

  // Function to insert an edge into the graph
  void insertEdge(int source, int destination, int weight, bool isDirected) {
    if (isDirected) {
      // For directed graph, only one entry is added for the source to
      // destination
      adjacencyList[source].push_back({destination, weight});
    } else {
      // For undirected graph, entries are added for both source to destination
      // and destination to source
      adjacencyList[source].push_back({destination, weight});
      adjacencyList[destination].push_back({source, weight});
    }
  }

  // Function to print the adjacency list
  void printAdjacencyList() {
    for (auto vertex : adjacencyList) {
      cout << vertex.first << " : ";
      for (auto neighbor : vertex.second) {
        cout << " { " << neighbor.first << " , " << neighbor.second << " } ";
      }
      cout << endl;
    }
  }

  // NOTE: unlike directed graphs here we can't use topological sort to get the
  // element in a dependency order
  // -> so we use min min-heap or set to get the node with the min distance .
  // -> isentially it's bfs only but here we are using set instead of queue .

  // Function to find the shortest paths using Dijkstra's algorithm
  vector<int> dijkstrasShortestPath(int source, int numberOfNodes) {

    // Vector to store the shortest distances from the source to each node
    // NOTE: using unordered_map could be a better / vercitle chaoice
    // -> as we won't need to handle the indexes manually then
    vector<int> shortestDistances(numberOfNodes + 1, INT_MAX);

    // Set to keep track of nodes and their distances, sorted by distance
    // NOTE: using min-heap could be a better chaoice here
    //  -> but then we'll have to write a custom comparator for it .
    set<pair<int, int>> nodesSet;

    // insert a source node into set and mark it's distance as 0
    nodesSet.insert({0, source});
    shortestDistances[source] = 0;

    // Dijkstra's algorithm
    while (!nodesSet.empty()) {

      // Get the node with the smallest distance
      auto currentNode = nodesSet.begin();

      // as a .begin() returns an itirator we need to dereference it with *
      auto currentPair = *(currentNode);

      // get the current node value and it's shortest distance so far
      int currentNodeValue = currentPair.second;
      int currentNodeDistance = currentPair.first;

      // Remove the current node from the set
      nodesSet.erase(nodesSet.begin());

      // Iterate over neighbors of the current node
      for (auto neighborPair : adjacencyList[currentNodeValue]) {

        // take the neighborDistance and neighborNodeValue out of neighborPair
        int neighborNodeValue = neighborPair.first;
        int neighborDistance = neighborPair.second;

        // Update the distance if the currentNodeDistance in addition to the
        // distance to the neighbor from the current node is smaller to the
        // distance of the neighbor.
        if (currentNodeDistance + neighborDistance <
            shortestDistances[neighborNodeValue]) {

          // Remove the previous entry for the neighbor from the set
          auto previousEntry = nodesSet.find(
              {shortestDistances[neighborNodeValue], neighborNodeValue});

          // if the previous entry of a neighbor pair is found erase it
          if (previousEntry != nodesSet.end()) {
            nodesSet.erase(previousEntry);
          }

          // Update the shortest distance for the neighbor node
          shortestDistances[neighborNodeValue] =
              currentNodeDistance + neighborDistance;

          // insert the updated entry back into the set for further processing
          // NOTE: we are inserting this updated neighbor into the set to
          // process it's neighbors and recalculate their distances accordingly.
          nodesSet.insert(
              {shortestDistances[neighborNodeValue], neighborNodeValue});
        }
      }
    }
    return shortestDistances;
  }
};

int main() {

  // Create a directed weighted graph object
  DirectedWeightedGraph weightedGraph;

  // Add edges to the graph
  weightedGraph.insertEdge(1, 6, 14, false);
  weightedGraph.insertEdge(1, 3, 9, false);
  weightedGraph.insertEdge(1, 2, 7, false);
  weightedGraph.insertEdge(2, 3, 10, false);
  weightedGraph.insertEdge(2, 4, 15, false);
  weightedGraph.insertEdge(3, 4, 11, false);
  weightedGraph.insertEdge(6, 3, 2, false);
  weightedGraph.insertEdge(6, 5, 9, false);
  weightedGraph.insertEdge(5, 4, 6, false);

  // Specify the source node and the total number of nodes in the graph
  int sourceNode = 6;
  int totalNodes = 6;

  // Find the shortest paths from the source to all nodes
  vector<int> shortestPaths =
      weightedGraph.dijkstrasShortestPath(sourceNode, totalNodes);

  // Print the adjacency list of the graph
  // weightedGraph.printAdjacencyList();

  // Display the shortest paths from the source to each node
  cout << "Shortest path from " << sourceNode << " to each node is : " << endl;

  // Print the shortest path lengths
  for (int i = 0; i < shortestPaths.size(); i++) {
    cout << i << " -> " << shortestPaths[i] << endl;
  }
  cout << endl;
}

This output indicates the shortest distance from node 6 to all other nodes. Note that 2147483647 (equivalent to INT_MAX) indicates that a node is unreachable from the source.

Key Notes:

• Set vs Min-Heap: While the code uses a set to get the minimum distance node, a min-heap (priority queue) could be more efficient, albeit with additional complexity.
• Handling Large Graphs: The algorithm works well for graphs without negative weights but may need adjustments for larger or more complex graphs, such as using a priority queue.

Time Complexity:

• Dijkstra's Algorithm: O((V + E) log V) where V is the number of vertices and E is the number of edges.

Space Complexity:

• Dijkstra's Algorithm: O(V + E) for storing the graph, distances, and the set.