Interactive Visualizer
Try out Dijkstra's algorithm with this interactive visualizer. Select a source and target node, then click "Run" to see the algorithm in action.
Unvisited
Current
In Queue
Visited
Shortest Path
Current:-
Visited:0
Click "Run" to start the visualization
How It Works
1. Initialize distances: source = 0, all others = infinity
2. Create a priority queue and add the source node
3. While the queue is not empty:
a. Extract the node with the minimum distance
b. For each neighbor of the current node:
- Calculate the tentative distance through current node
- If it's less than the known distance, update it
- Add the neighbor to the queue
4. Return the shortest distances to all nodes
Note: Dijkstra's algorithm only works with non-negative edge weights
Time & Space Complexity
Time Complexity:
- With binary heap: O((V + E) log V)
- With Fibonacci heap: O(E + V log V)
- With adjacency matrix: O(V²)
Where V = number of vertices, E = number of edges
Space Complexity:
- O(V) for distance array and priority queue
Dijkstra's Algorithm is:
- Greedy (always picks the minimum distance node)
- Optimal (guarantees shortest path with non-negative weights)
- Single-source (finds paths from one source to all nodes)
JavaScript Implementation
// Using a priority queue (min-heap)
function dijkstra(graph, source) {
const distances = {};
const previous = {};
const pq = new MinPriorityQueue();
// Initialize distances
for (const vertex in graph) {
distances[vertex] = Infinity;
previous[vertex] = null;
}
distances[source] = 0;
pq.enqueue(source, 0);
while (!pq.isEmpty()) {
const { element: current } = pq.dequeue();
for (const [neighbor, weight] of Object.entries(graph[current])) {
const distance = distances[current] + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
previous[neighbor] = current;
pq.enqueue(neighbor, distance);
}
}
}
return { distances, previous };
}
// Simple implementation without priority queue (O(V²))
function dijkstraSimple(graph, source) {
const nodes = Object.keys(graph);
const distances = {};
const visited = new Set();
nodes.forEach(node => distances[node] = Infinity);
distances[source] = 0;
while (visited.size < nodes.length) {
// Find unvisited node with minimum distance
let minNode = null;
let minDist = Infinity;
for (const node of nodes) {
if (!visited.has(node) && distances[node] < minDist) {
minDist = distances[node];
minNode = node;
}
}
if (minNode === null) break;
visited.add(minNode);
// Update distances to neighbors
for (const [neighbor, weight] of Object.entries(graph[minNode])) {
const newDist = distances[minNode] + weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
}
}
}
return distances;
}
// Usage
const graph = {
A: { B: 4, C: 2 },
B: { A: 4, C: 1, D: 5 },
C: { A: 2, B: 1, D: 8, E: 10 },
D: { B: 5, C: 8, E: 2 },
E: { C: 10, D: 2 }
};
console.log(dijkstra(graph, 'A'));
Python Implementation
import heapq
from collections import defaultdict
def dijkstra(graph, source):
# Initialize distances
distances = {node: float('inf') for node in graph}
distances[source] = 0
previous = {node: None for node in graph}
# Priority queue: (distance, node)
pq = [(0, source)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
for neighbor, weight in graph[current].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
return distances, previous
# Reconstruct the shortest path
def get_path(previous, target):
path = []
current = target
while current is not None:
path.append(current)
current = previous[current]
return path[::-1]
# Usage
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 1, 'D': 5},
'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
'D': {'B': 5, 'C': 8, 'E': 2},
'E': {'C': 10, 'D': 2}
}
distances, previous = dijkstra(graph, 'A')
print(f"Shortest distances: {distances}")
print(f"Path to E: {get_path(previous, 'E')}")
Java Implementation
import java.util.*;
public class Dijkstra {
public static Map<String, Integer> dijkstra(
Map<String, Map<String, Integer>> graph, String source) {
Map<String, Integer> distances = new HashMap<>();
Map<String, String> previous = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a[0])
);
Set<String> visited = new HashSet<>();
// Initialize distances
for (String node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(source, 0);
pq.offer(new int[]{0, source.hashCode()});
// Map for quick lookup
Map<Integer, String> hashToNode = new HashMap<>();
for (String node : graph.keySet()) {
hashToNode.put(node.hashCode(), node);
}
while (!pq.isEmpty()) {
int[] curr = pq.poll();
String current = hashToNode.get(curr[1]);
if (visited.contains(current)) continue;
visited.add(current);
for (Map.Entry<String, Integer> entry :
graph.get(current).entrySet()) {
String neighbor = entry.getKey();
int weight = entry.getValue();
int distance = distances.get(current) + weight;
if (distance < distances.get(neighbor)) {
distances.put(neighbor, distance);
previous.put(neighbor, current);
pq.offer(new int[]{distance, neighbor.hashCode()});
}
}
}
return distances;
}
}
C++ Implementation
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;
typedef pair<int, int> pii; // (distance, node)
vector<int> dijkstra(vector<vector<pii>>& graph, int source) {
int n = graph.size();
vector<int> distances(n, numeric_limits<int>::max());
vector<int> previous(n, -1);
// Min-heap priority queue
priority_queue<pii, vector<pii>, greater<pii>> pq;
distances[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [dist, current] = pq.top();
pq.pop();
if (dist > distances[current]) continue;
for (auto& [neighbor, weight] : graph[current]) {
int newDist = distances[current] + weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
previous[neighbor] = current;
pq.push({newDist, neighbor});
}
}
}
return distances;
}
// Usage
int main() {
// Graph with 5 nodes (0-4)
vector<vector<pii>> graph(5);
graph[0] = {{1, 4}, {2, 2}};
graph[1] = {{0, 4}, {2, 1}, {3, 5}};
graph[2] = {{0, 2}, {1, 1}, {3, 8}, {4, 10}};
graph[3] = {{1, 5}, {2, 8}, {4, 2}};
graph[4] = {{2, 10}, {3, 2}};
vector<int> distances = dijkstra(graph, 0);
return 0;
}
Graph Representations
# Adjacency List (recommended for sparse graphs)
graph_adj_list = {
'A': {'B': 4, 'C': 2},
'B': {'C': 1, 'D': 5},
'C': {'D': 8},
'D': {}
}
# Adjacency Matrix (better for dense graphs)
# A B C D
# A [[0, 4, 2, 0],
# B [0, 0, 1, 5],
# C [0, 0, 0, 8],
# D [0, 0, 0, 0]]
# Edge List
edges = [
('A', 'B', 4),
('A', 'C', 2),
('B', 'C', 1),
('B', 'D', 5),
('C', 'D', 8)
]
# Convert edge list to adjacency list
def edges_to_adj_list(edges):
graph = defaultdict(dict)
for u, v, weight in edges:
graph[u][v] = weight
# For undirected graph, also add:
# graph[v][u] = weight
return graph
Handling Edge Cases
def dijkstra_safe(graph, source, target=None):
# Check if source exists
if source not in graph:
raise ValueError(f"Source node '{source}' not in graph")
distances = {node: float('inf') for node in graph}
distances[source] = 0
pq = [(0, source)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
# Early termination if target is reached
if target and current == target:
return distances[target]
for neighbor, weight in graph[current].items():
# Check for negative weights
if weight < 0:
raise ValueError("Negative weights not supported")
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
Bidirectional Dijkstra
# Faster for single source-target queries
def bidirectional_dijkstra(graph, reverse_graph, source, target):
if source == target:
return 0, [source]
# Forward and backward searches
dist_f = {source: 0}
dist_b = {target: 0}
pq_f = [(0, source)]
pq_b = [(0, target)]
visited_f = set()
visited_b = set()
best_dist = float('inf')
meeting_node = None
while pq_f or pq_b:
# Expand forward
if pq_f:
d, u = heapq.heappop(pq_f)
if u in visited_f:
continue
visited_f.add(u)
if u in visited_b:
total = dist_f[u] + dist_b[u]
if total < best_dist:
best_dist = total
meeting_node = u
for v, w in graph[u].items():
if dist_f.get(v, float('inf')) > d + w:
dist_f[v] = d + w
heapq.heappush(pq_f, (d + w, v))
# Expand backward (similar logic)
if pq_b:
d, u = heapq.heappop(pq_b)
if u in visited_b:
continue
visited_b.add(u)
if u in visited_f:
total = dist_f[u] + dist_b[u]
if total < best_dist:
best_dist = total
meeting_node = u
for v, w in reverse_graph[u].items():
if dist_b.get(v, float('inf')) > d + w:
dist_b[v] = d + w
heapq.heappush(pq_b, (d + w, v))
return best_dist, meeting_node
Dijkstra vs Other Algorithms
Algorithm | Weights | Time | Use Case
------------------|--------------|----------------|---------------------------
Dijkstra | Non-negative | O((V+E) log V) | Single-source shortest path
Bellman-Ford | Any | O(V × E) | Negative weights, detect cycles
Floyd-Warshall | Any | O(V³) | All-pairs shortest paths
A* Search | Non-negative | O(E) | Single-pair with heuristic
BFS | Unweighted | O(V + E) | Unweighted graphs
When to use Dijkstra:
✓ Finding shortest path from one source to all nodes
✓ Graph has non-negative edge weights
✓ Need optimal solution (not approximation)
✗ Graph has negative weights (use Bellman-Ford)
✗ Need all-pairs shortest paths (use Floyd-Warshall)
✗ Unweighted graph (use BFS - simpler & faster)
Common Applications
1. GPS Navigation
- Finding shortest/fastest route between locations
2. Network Routing
- OSPF protocol uses Dijkstra for packet routing
3. Social Networks
- Finding degrees of separation between users
4. Games
- Pathfinding for characters/units (often combined with A*)
5. Flight Planning
- Finding optimal flight routes with layovers
6. Robotics
- Path planning for autonomous navigation