AntInLoop

Dijkstra's Algorithm Code Implementations

Complete Dijkstra's Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Dijkstra's Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Dijkstra's Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <limits>
#include <algorithm>

class DijkstrasAlgorithm {
public:
    static std::unordered_map<int, int> dijkstrasAlgorithm(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start) {
        std::unordered_map<int, int> distances;
        std::unordered_map<int, int> previous;
        std::unordered_set<int> unvisited;
        
        // Initialize distances
        for (const auto& [vertex, neighbors] : graph) {
            distances[vertex] = std::numeric_limits<int>::max();
            unvisited.insert(vertex);
        }
        distances[start] = 0;
        
        while (!unvisited.empty()) {
            // Find vertex with minimum distance
            int current = -1;
            int minDistance = std::numeric_limits<int>::max();
            
            for (int vertex : unvisited) {
                if (distances[vertex] < minDistance) {
                    minDistance = distances[vertex];
                    current = vertex;
                }
            }
            
            if (current == -1) break;
            
            unvisited.erase(current);
            
            // Update distances to neighbors
            auto it = graph.find(current);
            if (it != graph.end()) {
                for (const auto& [neighbor, weight] : it->second) {
                    if (unvisited.find(neighbor) != unvisited.end()) {
                        int newDistance = distances[current] + weight;
                        if (newDistance < distances[neighbor]) {
                            distances[neighbor] = newDistance;
                            previous[neighbor] = current;
                        }
                    }
                }
            }
        }
        
        return distances;
    }
    
    // Dijkstra's with priority queue (more efficient)
    static std::unordered_map<int, int> dijkstrasAlgorithmWithPriorityQueue(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start) {
        std::unordered_map<int, int> distances;
        std::unordered_map<int, int> previous;
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
        
        // Initialize distances
        for (const auto& [vertex, neighbors] : graph) {
            distances[vertex] = std::numeric_limits<int>::max();
        }
        distances[start] = 0;
        pq.push({0, start});
        
        while (!pq.empty()) {
            auto [distance, current] = pq.top();
            pq.pop();
            
            if (distance > distances[current]) continue;
            
            auto it = graph.find(current);
            if (it != graph.end()) {
                for (const auto& [neighbor, weight] : it->second) {
                    int newDistance = distances[current] + weight;
                    if (newDistance < distances[neighbor]) {
                        distances[neighbor] = newDistance;
                        previous[neighbor] = current;
                        pq.push({newDistance, neighbor});
                    }
                }
            }
        }
        
        return distances;
    }
    
    // Get shortest path from start to end
    static std::vector<int> getShortestPath(const std::unordered_map<int, std::unordered_map<int, int>>& graph, int start, int end) {
        auto distances = dijkstrasAlgorithm(graph, start);
        std::unordered_map<int, int> previous;
        
        if (distances[end] == std::numeric_limits<int>::max()) {
            return {}; // No path exists
        }
        
        std::vector<int> path;
        int current = end;
        
        while (current != start) {
            path.insert(path.begin(), current);
            current = previous[current];
        }
        path.insert(path.begin(), start);
        
        return path;
    }
};

JAVA Implementation

// Dijkstra's Algorithm Implementation in Java
import java.util.*;

public class DijkstrasAlgorithm {
    public static Map<Integer, Integer> dijkstrasAlgorithm(Map<Integer, Map<Integer, Integer>> graph, int start) {
        Map<Integer, Integer> distances = new HashMap<>();
        Map<Integer, Integer> previous = new HashMap<>();
        Set<Integer> unvisited = new HashSet<>();
        
        // Initialize distances
        for (int vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
            unvisited.add(vertex);
        }
        distances.put(start, 0);
        
        while (!unvisited.isEmpty()) {
            // Find vertex with minimum distance
            int current = -1;
            int minDistance = Integer.MAX_VALUE;
            
            for (int vertex : unvisited) {
                if (distances.get(vertex) < minDistance) {
                    minDistance = distances.get(vertex);
                    current = vertex;
                }
            }
            
            if (current == -1) break;
            
            unvisited.remove(current);
            
            // Update distances to neighbors
            Map<Integer, Integer> neighbors = graph.getOrDefault(current, new HashMap<>());
            for (Map.Entry<Integer, Integer> entry : neighbors.entrySet()) {
                int neighbor = entry.getKey();
                int weight = entry.getValue();
                
                if (unvisited.contains(neighbor)) {
                    int newDistance = distances.get(current) + weight;
                    if (newDistance < distances.get(neighbor)) {
                        distances.put(neighbor, newDistance);
                        previous.put(neighbor, current);
                    }
                }
            }
        }
        
        return distances;
    }
    
    // Dijkstra's with priority queue (more efficient)
    public static Map<Integer, Integer> dijkstrasAlgorithmWithPriorityQueue(Map<Integer, Map<Integer, Integer>> graph, int start) {
        Map<Integer, Integer> distances = new HashMap<>();
        Map<Integer, Integer> previous = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        
        // Initialize distances
        for (int vertex : graph.keySet()) {
            distances.put(vertex, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        pq.offer(new int[]{start, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int vertex = current[0];
            int distance = current[1];
            
            if (distance > distances.get(vertex)) continue;
            
            Map<Integer, Integer> neighbors = graph.getOrDefault(vertex, new HashMap<>());
            for (Map.Entry<Integer, Integer> entry : neighbors.entrySet()) {
                int neighbor = entry.getKey();
                int weight = entry.getValue();
                
                int newDistance = distances.get(vertex) + weight;
                if (newDistance < distances.get(neighbor)) {
                    distances.put(neighbor, newDistance);
                    previous.put(neighbor, vertex);
                    pq.offer(new int[]{neighbor, newDistance});
                }
            }
        }
        
        return distances;
    }
    
    // Get shortest path from start to end
    public static List<Integer> getShortestPath(Map<Integer, Map<Integer, Integer>> graph, int start, int end) {
        Map<Integer, Integer> distances = dijkstrasAlgorithm(graph, start);
        Map<Integer, Integer> previous = new HashMap<>();
        
        if (distances.get(end) == Integer.MAX_VALUE) {
            return null; // No path exists
        }
        
        List<Integer> path = new ArrayList<>();
        int current = end;
        
        while (current != start) {
            path.add(0, current);
            current = previous.get(current);
        }
        path.add(0, start);
        
        return path;
    }
}

JAVASCRIPT Implementation

// Dijkstra's Algorithm Implementation in JavaScript
function dijkstrasAlgorithm(graph, start) {
  const distances = {};
  const previous = {};
  const unvisited = new Set();
  
  // Initialize distances
  for (const vertex in graph) {
    distances[vertex] = Infinity;
    unvisited.add(vertex);
  }
  distances[start] = 0;
  
  while (unvisited.size > 0) {
    // Find vertex with minimum distance
    let current = null;
    let minDistance = Infinity;
    
    for (const vertex of unvisited) {
      if (distances[vertex] < minDistance) {
        minDistance = distances[vertex];
        current = vertex;
      }
    }
    
    if (current === null) break;
    
    unvisited.delete(current);
    
    // Update distances to neighbors
    const neighbors = graph[current] || {};
    for (const neighbor in neighbors) {
      if (unvisited.has(neighbor)) {
        const newDistance = distances[current] + neighbors[neighbor];
        if (newDistance < distances[neighbor]) {
          distances[neighbor] = newDistance;
          previous[neighbor] = current;
        }
      }
    }
  }
  
  return { distances, previous };
}

// Dijkstra's with priority queue (more efficient)
function dijkstrasAlgorithmWithPriorityQueue(graph, start) {
  const distances = {};
  const previous = {};
  const pq = new PriorityQueue();
  
  // Initialize distances
  for (const vertex in graph) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  pq.enqueue(start, 0);
  
  while (!pq.isEmpty()) {
    const { element: current, priority: currentDistance } = pq.dequeue();
    
    if (currentDistance > distances[current]) continue;
    
    const neighbors = graph[current] || {};
    for (const neighbor in neighbors) {
      const newDistance = distances[current] + neighbors[neighbor];
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance;
        previous[neighbor] = current;
        pq.enqueue(neighbor, newDistance);
      }
    }
  }
  
  return { distances, previous };
}

// Get shortest path from start to end
function getShortestPath(graph, start, end) {
  const { distances, previous } = dijkstrasAlgorithm(graph, start);
  
  if (distances[end] === Infinity) {
    return null; // No path exists
  }
  
  const path = [];
  let current = end;
  
  while (current !== undefined) {
    path.unshift(current);
    current = previous[current];
  }
  
  return {
    path,
    distance: distances[end]
  };
}

// Priority Queue implementation
class PriorityQueue {
  constructor() {
    this.values = [];
  }
  
  enqueue(element, priority) {
    this.values.push({ element, priority });
    this.sort();
  }
  
  dequeue() {
    return this.values.shift();
  }
  
  isEmpty() {
    return this.values.length === 0;
  }
  
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

PYTHON Implementation

# Dijkstra's Algorithm Implementation in Python
import heapq
from collections import defaultdict

def dijkstras_algorithm(graph, start):
    distances = {}
    previous = {}
    unvisited = set()
    
    # Initialize distances
    for vertex in graph:
        distances[vertex] = float('inf')
        unvisited.add(vertex)
    distances[start] = 0
    
    while unvisited:
        # Find vertex with minimum distance
        current = min(unvisited, key=lambda v: distances[v])
        
        if distances[current] == float('inf'):
            break
        
        unvisited.remove(current)
        
        # Update distances to neighbors
        neighbors = graph.get(current, {})
        for neighbor, weight in neighbors.items():
            if neighbor in unvisited:
                new_distance = distances[current] + weight
                if new_distance < distances[neighbor]:
                    distances[neighbor] = new_distance
                    previous[neighbor] = current
    
    return distances, previous

# Dijkstra's with priority queue (more efficient)
def dijkstras_algorithm_with_priority_queue(graph, start):
    distances = {}
    previous = {}
    pq = [(0, start)]
    
    # Initialize distances
    for vertex in graph:
        distances[vertex] = float('inf')
    distances[start] = 0
    
    while pq:
        current_distance, current = heapq.heappop(pq)
        
        if current_distance > distances[current]:
            continue
        
        neighbors = graph.get(current, {})
        for neighbor, weight in neighbors.items():
            new_distance = distances[current] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous[neighbor] = current
                heapq.heappush(pq, (new_distance, neighbor))
    
    return distances, previous

# Get shortest path from start to end
def get_shortest_path(graph, start, end):
    distances, previous = dijkstras_algorithm(graph, start)
    
    if distances[end] == float('inf'):
        return None  # No path exists
    
    path = []
    current = end
    
    while current is not None:
        path.insert(0, current)
        current = previous.get(current)
    
    return {
        'path': path,
        'distance': distances[end]
    }

# Dijkstra's for single source shortest path
def dijkstras_single_source(graph, start):
    distances, previous = dijkstras_algorithm_with_priority_queue(graph, start)
    return distances