Hello! In this article, I would like to talk about the preparation process for algorithm exams for employment. In particular, we will delve deeply into the problem of finding the shortest path<\/strong>. This problem can be encountered in various situations, and the shortest path algorithm, a fundamental concept in graph theory, is frequently asked in job interviews.<\/p>\n The shortest path problem is the problem of finding the shortest path between two nodes in a given graph. Here, the graph is a mathematical representation of networks such as roads and communication networks, composed of vertices and edges. We can use various algorithms to solve this problem, and we will focus on Dijkstra’s algorithm here.<\/p>\n Dijkstra’s algorithm is an efficient algorithm for finding the shortest path from a single vertex to all other vertices in a weighted graph. The algorithm works as follows:<\/p>\n In this lecture, we will address the problem of finding the shortest path between two vertices when given a graph. The problem can be summarized in the following form:<\/p>\n Given a directed graph and its weights, determine the shortest path distance from vertex Input:<\/p>\n Output: Explanation: The paths from vertex 0 to vertex 4 are 0\u21921\u21922\u21924 or 0\u21922\u21924, and the shortest distance of the two paths is 5.<\/p>\n<\/div>\n First, to solve the above problem, we need to set up the graph in an appropriate data structure. Generally, using an adjacency list is efficient in terms of memory and processing speed. In Python, this can be implemented using a dictionary.<\/p>\n Next, the libraries needed to implement Dijkstra’s algorithm are as follows:<\/p>\n Here, Now, let’s write the complete code to find the shortest path:<\/p>\n The code above uses Dijkstra's algorithm to find the shortest path in the given graph. Each comment allows you to understand the code step by step, but to summarize briefly:<\/p>\nDefinition of the Shortest Path Problem<\/h2>\n
Understanding Dijkstra’s Algorithm<\/h3>\n
\n
Problem Statement<\/h2>\n
Problem: Finding the Shortest Path<\/h3>\n
S<\/code> to vertex T<\/code>.<\/p>\n5 7\n0 1 2\n0 2 3\n1 2 1\n1 3 5\n2 4 2\n3 4 1\n4 3 3\n0 4<\/code><\/pre>\n5<\/code><\/p>\nProblem-Solving Process<\/h2>\n
1. Setting Up the Graph Structure<\/h3>\n
2. Implementing Dijkstra’s Algorithm<\/h3>\n
import heapq\nimport sys\nfrom collections import defaultdict\n<\/code><\/pre>\nheapq<\/code> is used for the priority queue, and defaultdict<\/code> is used to easily implement the adjacency list.<\/p>\n3. Example Python Code<\/h3>\n
\ndef dijkstra(graph, start, end):\n # Initialize distances\n distance = {node: float('inf') for node in graph}\n distance[start] = 0\n priority_queue = [(0, start)] # (distance, vertex)\n\n while priority_queue:\n current_distance, current_node = heapq.heappop(priority_queue)\n\n # Ignore if a greater value than the current node's distance comes in\n if current_distance > distance[current_node]:\n continue\n\n # Visit neighboring nodes\n for neighbor, weight in graph[current_node]:\n distance_via_neighbor = current_distance + weight\n if distance_via_neighbor < distance[neighbor]:\n distance[neighbor] = distance_via_neighbor\n heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))\n\n return distance[end]\n\n# Define the graph\ngraph = defaultdict(list)\nedges = [\n (0, 1, 2),\n (0, 2, 3),\n (1, 2, 1),\n (1, 3, 5),\n (2, 4, 2),\n (3, 4, 1),\n (4, 3, 3)\n]\n\nfor u, v, w in edges:\n graph[u].append((v, w))\n\n# Calculate the shortest path\nstart, end = 0, 4\nresult = dijkstra(graph, start, end)\nprint(result) # Output result: 5\n<\/code><\/pre>\n4. Code Explanation<\/h2>\n