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.<\/p>\n
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.<\/p>\n
Given the number of cities For example, let’s assume the following input is given:<\/p>\n In the above example, the lengths of the shortest paths from city 1 to the other cities are as follows:<\/p>\n Since we start from city 1, the length of the shortest path includes 0 for itself and the shortest distances to the other cities.<\/p>\n To solve this problem, we can use the Dijkstra Algorithm<\/strong>. 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.<\/p>\n 1) Initialization: Set the distance of the starting city to 0 and the distances of the remaining cities to infinity. Now, let’s implement the above algorithm in JavaScript.<\/p>\n 1) Initialize the number of nodes and edges. 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.<\/p>\n 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.<\/p>\n I hope this is helpful, and I look forward to meeting you with more interesting topics in the next lecture. Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"n<\/code> and the number of roads m<\/code>, find the shortest path from a specific city k<\/code> to all other cities. The information about the roads is given as a weight w<\/code> connecting u<\/code> and v<\/code>. The weight represents the length of the road.<\/p>\nInput Format<\/h3>\n
\nn, m, k\nu1, v1, w1\nu2, v2, w2\n...\num, vm, wm\n<\/code><\/pre>\nOutput Format<\/h3>\n
\nArray of the lengths of the shortest paths\n<\/code><\/pre>\n\n5 6 1\n1 2 2\n1 3 3\n2 3 1\n2 4 2\n3 4 4\n4 5 1\n<\/code><\/pre>\n\n0\n2\n3\n4\n5\n<\/code><\/pre>\nSolution Approach<\/h2>\n
Description of the Dijkstra Algorithm<\/h3>\n
\n2) Storing visited cities: Keep track of visited cities separately to prevent duplicate calculations.
\n3) Using a priority queue: Select the city with the shortest distance to proceed. Update the distances of the neighboring cities.
\n4) Repeat: Continue the above process until all cities are visited.<\/p>\nJavaScript Implementation Example<\/h2>\n
\nfunction dijkstra(n, edges, start) {\n const INF = Infinity;\n const graph = Array.from({ length: n + 1 }, () => []);\n const dist = Array(n + 1).fill(INF);\n dist[start] = 0;\n const pq = new MinPriorityQueue();\n\n edges.forEach(([u, v, w]) => {\n graph[u].push([v, w]);\n graph[v].push([u, w]); \/\/ For undirected graphs\n });\n\n pq.enqueue(start, 0);\n\n while (!pq.isEmpty()) {\n const { element: current, priority: currentDist } = pq.dequeue();\n \n if (currentDist > dist[current]) continue; \/\/ If already visited with the shortest distance\n \n for (const [neighbor, weight] of graph[current]) {\n const newDist = currentDist + weight;\n if (newDist < dist[neighbor]) {\n dist[neighbor] = newDist;\n pq.enqueue(neighbor, newDist);\n }\n }\n }\n return dist.slice(1); \/\/ Exclude index 0\n}\n\nclass MinPriorityQueue {\n constructor() {\n this.items = [];\n }\n\n enqueue(element, priority) {\n this.items.push({ element, priority });\n this.items.sort((a, b) => a.priority - b.priority);\n }\n\n dequeue() {\n return this.items.shift(); \/\/ Returns the one with the lowest priority\n }\n\n isEmpty() {\n return this.items.length === 0;\n }\n}\n\n\/\/ Example usage\nconst n = 5;\nconst edges = [\n [1, 2, 2],\n [1, 3, 3],\n [2, 3, 1],\n [2, 4, 2],\n [3, 4, 4],\n [4, 5, 1]\n];\nconst start = 1;\nconsole.log(dijkstra(n, edges, start)); \/\/ [0, 2, 3, 4, 5]\n<\/code><\/pre>\nSummary of the Problem Solving Process<\/h2>\n
\n2) Represent the roads (edges) between cities as a graph.
\n3) Use the Dijkstra algorithm to calculate the shortest paths.
\n4) Output the results of the shortest paths.<\/p>\nConclusion<\/h2>\n