Problem Description
There is a given undirected graph. The graph consists of nodes and edges,
and each edge has a weight. Let’s solve the problem of finding the shortest path from the starting node
to all other nodes. This algorithm can be solved using Dijkstra’s algorithm.
Problem Definition
Let’s assume the graph below. The number of nodes is n, and the number of edges is e.
Input
n = 6
e = 9
edges = [
[1, 2, 1],
[1, 3, 4],
[2, 3, 2],
[2, 4, 5],
[3, 4, 1],
[4, 5, 3],
[3, 5, 6],
[5, 6, 2],
[4, 6, 1]
]
start = 1
Write a function that finds the shortest path from the start node (node 1) to other nodes in the given graph.
The function should return an array of the minimum distances to each node.
Algorithm Overview
Dijkstra’s algorithm is used to find the shortest path from a given node to all other nodes in graph theory.
This algorithm efficiently finds the shortest path using a priority queue. The following steps are followed
in the actual implementation.
- Initialize the shortest distance array for each node. Set the initial value to infinity, but set the distance of the starting node to 0.
- Add the starting node to the priority queue (min-heap).
- Repeat while the queue is not empty.
- Extract the node with the shortest distance from the queue and update the distances for its adjacent nodes. If the new distance is smaller than the existing distance, add it to the priority queue.
- Return the array after calculating the shortest distances for all nodes.
JavaScript Implementation
Now, let’s implement a JavaScript function that solves the above problem based on the algorithm.
function dijkstra(n, edges, start) {
// 1. Construct the graph
const graph = Array.from({ length: n + 1 }, () => []);
for (const [u, v, weight] of edges) {
graph[u].push({ node: v, weight });
graph[v].push({ node: u, weight }); // undirected
}
// 2. Initialize shortest distance
const distance = Array(n + 1).fill(Infinity);
distance[start] = 0;
// 3. Initialize the priority queue
const pq = new MinHeap();
pq.insert({ node: start, weight: 0 });
while (!pq.isEmpty()) {
const { node: currentNode, weight: currentWeight } = pq.extractMin();
if (currentWeight > distance[currentNode]) continue;
// 4. Process adjacent nodes
for (const { node: neighbor, weight } of graph[currentNode]) {
const newDistance = currentWeight + weight;
if (newDistance < distance[neighbor]) {
distance[neighbor] = newDistance;
pq.insert({ node: neighbor, weight: newDistance });
}
}
}
return distance.slice(1); // Return distance array excluding the start node
}
// Min-heap class (priority queue implementation)
class MinHeap {
constructor() {
this.heap = [];
}
insert({ node, weight }) {
this.heap.push({ node, weight });
this.bubbleUp();
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].weight >= this.heap[parentIndex].weight) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin() {
if (this.heap.length === 1) return this.heap.pop();
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
bubbleDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild.weight < element.weight) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild.weight < element.weight) ||
(swap !== null && rightChild.weight < leftChild.weight)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
isEmpty() {
return this.heap.length === 0;
}
}
Test
To test the above code, you can call the function as follows to check the result.
const n = 6;
const edges = [
[1, 2, 1],
[1, 3, 4],
[2, 3, 2],
[2, 4, 5],
[3, 4, 1],
[4, 5, 3],
[3, 5, 6],
[5, 6, 2],
[4, 6, 1]
];
const start = 1;
const distances = dijkstra(n, edges, start);
console.log(distances); // [0, 1, 3, 4, 6, 7]
Conclusion
Dijkstra's algorithm is a very useful algorithm for finding the shortest path. Through the problems and code discussed in this tutorial,
I hope you gained an understanding of the basic concepts of Dijkstra's algorithm and its implementation in JavaScript. A deeper understanding of algorithms will help enhance your coding test skills and problem-solving abilities.
Continue to study and practice various algorithms!