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