Implement Dijkstra’s Algorithm in JavaScript for Route Planning
Dijkstra’s algorithm is a cornerstone in graph theory that helps find the shortest path between nodes in a graph. Whether you’re developing a GPS navigation system, building a game map, or creating a logistics planner, mastering this algorithm empowers you to solve real-world route optimization problems efficiently.
1. What is Dijkstra’s Algorithm and Why Use It?
Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It’s widely used in routing and navigation systems, such as GPS apps, public transportation planners, and network routing protocols.
Given a start node and a weighted graph, the algorithm finds the minimum cost paths from that node to all others.
2. Representing the Graph in JavaScript
To implement the algorithm, let’s use an adjacency list to model the graph. Each node will map to an array of neighbor objects containing the destination and weight.
const graph = {
A: [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }],
B: [{ node: 'A', weight: 4 }, { node: 'C', weight: 3 }, { node: 'D', weight: 5 }],
C: [{ node: 'A', weight: 2 }, { node: 'B', weight: 3 }, { node: 'D', weight: 4 }, { node: 'E', weight: 3 }],
D: [{ node: 'B', weight: 5 }, { node: 'C', weight: 4 }, { node: 'E', weight: 1 }],
E: [{ node: 'C', weight: 3 }, { node: 'D', weight: 1 }]
};This structure is simple, intuitive, and easy to extend. It enables quick access to neighbors of any node, which makes it ideal for our pathfinding logic.
3. Building the Dijkstra’s Algorithm Logic
We’ll use a priority queue (or min-heap) to efficiently track the next node with the smallest distance. JavaScript doesn’t have a native priority queue, but for small graphs, we can simulate it using arrays with sorting.
function dijkstra(graph, start) {
const distances = {};
const visited = new Set();
const priorityQueue = [{ node: start, distance: 0 }];
// Initialize distances
for (const node in graph) {
distances[node] = Infinity;
}
distances[start] = 0;
while (priorityQueue.length > 0) {
// Sort queue based on distance (simulating min-heap)
priorityQueue.sort((a, b) => a.distance - b.distance);
const { node: currentNode } = priorityQueue.shift();
if (visited.has(currentNode)) continue;
visited.add(currentNode);
for (const neighbor of graph[currentNode]) {
const alt = distances[currentNode] + neighbor.weight;
if (alt < distances[neighbor.node]) {
distances[neighbor.node] = alt;
priorityQueue.push({ node: neighbor.node, distance: alt });
}
}
}
return distances;
}This function returns an object containing the shortest distances from the start node to every other node. Performance can be improved using a proper binary heap for larger datasets.
4. Adding Path Tracking to Recover Full Paths
In many real-world applications, knowing the shortest distance isn’t enough — we need the actual path. Let’s modify the function to track the previous node.
function dijkstraWithPaths(graph, start) {
const distances = {};
const previous = {};
const visited = new Set();
const priorityQueue = [{ node: start, distance: 0 }];
for (const node in graph) {
distances[node] = Infinity;
previous[node] = null;
}
distances[start] = 0;
while (priorityQueue.length > 0) {
priorityQueue.sort((a, b) => a.distance - b.distance);
const { node: currentNode } = priorityQueue.shift();
if (visited.has(currentNode)) continue;
visited.add(currentNode);
for (const neighbor of graph[currentNode]) {
const alt = distances[currentNode] + neighbor.weight;
if (alt < distances[neighbor.node]) {
distances[neighbor.node] = alt;
previous[neighbor.node] = currentNode;
priorityQueue.push({ node: neighbor.node, distance: alt });
}
}
}
return { distances, previous };
}To reconstruct the path from the start to a target node, you can backtrack using the previous object:
function getPath(previous, end) {
const path = [];
let current = end;
while (current) {
path.unshift(current);
current = previous[current];
}
return path;
}5. Real-World Use Case: Route Planning for Deliveries
Imagine you're building a delivery app that calculates the most efficient route between warehouses and customer addresses. You can represent intersections as nodes and roads as edges weighted by travel time or distance.
Example:
const result = dijkstraWithPaths(graph, 'A');
console.log('Shortest distance to E:', result.distances['E']);
console.log('Shortest path to E:', getPath(result.previous, 'E'));Output might be:
Shortest distance to E: 5
Shortest path to E: [ 'A', 'C', 'E' ]This technique scales well to model road networks and is extensible to handle more complex systems like traffic conditions or multi-modal transport.
6. Optimization Tips and Enhancements
- Use a Binary Heap or MinHeap for the priority queue to reduce time complexity from O(n²) to O((V+E) log V).
- Use adjacency maps instead of arrays for faster lookup when working with large graphs.
- For static graphs, precompute all pairs shortest paths if space allows (e.g., using Floyd-Warshall).
- Cache results if querying repeatedly from the same source node.
Dijkstra’s is a solid base algorithm for routing but can be enhanced further with A* for heuristic-based pathfinding or Bidirectional Dijkstra for large graphs requiring faster lookup between two endpoints.
7. Conclusion
Implementing Dijkstra’s algorithm in JavaScript opens doors to solving various real-world problems from logistics and navigation to simulation and games. By starting with a simple adjacency list and plain arrays, developers can learn the core concept and evolve it into a production-grade solution using heaps or specialized graph libraries.
Graph algorithms like Dijkstra’s are not just academic exercises — they’re practical tools in any developer’s toolkit. With JavaScript’s flexibility and ever-expanding ecosystem, it’s easier than ever to bring these algorithms to life on the web or server-side.
Now that you've learned how Dijkstra’s algorithm works, try expanding it with live visualizations or integrating it into a real mapping API!
Useful links:
