Hello! In this lecture, we will cover one of the JavaScript coding test problems for employment, ‘Finding the Shortest Path.’ This problem will be very helpful in understanding and utilizing the basic principles of algorithms and data structures. It is a common topic in coding interviews, and understanding priority queues and graph theory is essential.
Problem Description
We assume that we can represent the relationship between several cities and roads as a graph. Each city is represented as a node, and roads are represented as edges between nodes. We need to find the shortest path from one city to another.
Problem Definition
Given the number of cities n and the number of roads m, find the shortest path from a specific city k to all other cities. The information about the roads is given as a weight w connecting u and v. The weight represents the length of the road.
Input Format
n, m, k
u1, v1, w1
u2, v2, w2
...
um, vm, wm
Output Format
Array of the lengths of the shortest paths
For example, let’s assume the following input is given:
5 6 1
1 2 2
1 3 3
2 3 1
2 4 2
3 4 4
4 5 1
In the above example, the lengths of the shortest paths from city 1 to the other cities are as follows:
0
2
3
4
5
Since we start from city 1, the length of the shortest path includes 0 for itself and the shortest distances to the other cities.
Solution Approach
To solve this problem, we can use the Dijkstra Algorithm. The Dijkstra algorithm is used to find the shortest path from a specific starting node to all other nodes in a graph, utilizing a priority queue.
Description of the Dijkstra Algorithm
1) Initialization: Set the distance of the starting city to 0 and the distances of the remaining cities to infinity.
2) Storing visited cities: Keep track of visited cities separately to prevent duplicate calculations.
3) Using a priority queue: Select the city with the shortest distance to proceed. Update the distances of the neighboring cities.
4) Repeat: Continue the above process until all cities are visited.
JavaScript Implementation Example
Now, let’s implement the above algorithm in JavaScript.
function dijkstra(n, edges, start) {
const INF = Infinity;
const graph = Array.from({ length: n + 1 }, () => []);
const dist = Array(n + 1).fill(INF);
dist[start] = 0;
const pq = new MinPriorityQueue();
edges.forEach(([u, v, w]) => {
graph[u].push([v, w]);
graph[v].push([u, w]); // For undirected graphs
});
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const { element: current, priority: currentDist } = pq.dequeue();
if (currentDist > dist[current]) continue; // If already visited with the shortest distance
for (const [neighbor, weight] of graph[current]) {
const newDist = currentDist + weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
return dist.slice(1); // Exclude index 0
}
class MinPriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
this.items.push({ element, priority });
this.items.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.items.shift(); // Returns the one with the lowest priority
}
isEmpty() {
return this.items.length === 0;
}
}
// Example usage
const n = 5;
const edges = [
[1, 2, 2],
[1, 3, 3],
[2, 3, 1],
[2, 4, 2],
[3, 4, 4],
[4, 5, 1]
];
const start = 1;
console.log(dijkstra(n, edges, start)); // [0, 2, 3, 4, 5]
Summary of the Problem Solving Process
1) Initialize the number of nodes and edges.
2) Represent the roads (edges) between cities as a graph.
3) Use the Dijkstra algorithm to calculate the shortest paths.
4) Output the results of the shortest paths.
Conclusion
In this lecture, we learned how to implement graph algorithms in JavaScript through the ‘Finding the Shortest Path’ problem. The Dijkstra algorithm is simple to implement and can be applied to various problems, making it very useful. It often appears not only in coding tests but also in algorithm competitions, so be sure to master it.
Additionally, in order to gain a deeper understanding of algorithms, it is good to study various variations of the shortest path algorithms (such as the Bellman-Ford algorithm, Floyd-Warshall algorithm, etc.). By understanding the differences and use cases of these algorithms, you will gain a broader perspective.
I hope this is helpful, and I look forward to meeting you with more interesting topics in the next lecture. Thank you!