In this course, we will learn about algorithms to solve the critical path problem. The Critical Path shows the start and completion times of each task in project management, representing the longest path to complete the entire project. It is a very important concept in engineering and software projects and is one of the frequently tested topics in actual coding interviews.<\/p>\n
We aim to address the problem of finding the critical path when given a directed graph with the following structure. Each node in the graph represents a task, and edges indicate the precedence relationships between tasks. What we need to calculate is the minimum time required to complete all tasks.<\/p>\n
\nInput:\n- n (1 \u2264 n \u2264 100): Number of tasks\n- edges: A list representing the dependency relationships between tasks, where each element is a tuple (u, v, w), \n where u is the starting node of the task, v is the ending node of the task, and w is the time required to complete the task.\n\nOutput:\n- The longest time required to complete all tasks (length of the critical path)\n<\/pre>\nExample Input<\/h3>\n
\nn = 5\nedges = [\n (1, 2, 3),\n (1, 3, 2),\n (2, 4, 4),\n (3, 4, 5),\n (4, 5, 1)\n]\n<\/pre>\nExample Output<\/h3>\n
\n8\n<\/pre>\nProblem Solving and Approach<\/h2>\n
To solve this problem, we can implement it by following these steps.<\/p>\n
1. Representing the Directed Graph<\/h3>\n
First, we need to structure the graph based on the input edge information. To do this, we will construct the graph in the form of an adjacency list. We will also prepare an array to store the completion times of each task.<\/p>\n
from collections import defaultdict\nimport sys\n\ndef critical_path(n, edges):\n graph = defaultdict(list)\n in_degree = [0] * (n + 1)\n completion_time = [0] * (n + 1)\n\n # Construct the graph and calculate in-degrees\n for u, v, w in edges:\n graph[u].append((v, w))\n in_degree[v] += 1\n<\/code><\/pre>\n2. Topological Sorting<\/h3>\n
The next step is to perform a topological sort of the graph to safely process all tasks. Through topological sorting, we can determine the order in which each task should be completed while considering task dependencies.<\/p>\n
# Perform topological sort\n zero_degree_queue = []\n for i in range(1, n + 1):\n if in_degree[i] == 0:\n zero_degree_queue.append(i)\n \n topo_order = []\n while zero_degree_queue:\n node = zero_degree_queue.pop(0)\n topo_order.append(node)\n for neighbor, duration in graph[node]:\n in_degree[neighbor] -= 1\n if in_degree[neighbor] == 0:\n zero_degree_queue.append(neighbor)\n<\/code><\/pre>\n3. Calculating Minimum Duration<\/h3>\n
Now, we calculate the completion times for each task in the order determined by the topological sort. Each time we perform a task, we update the completion times of all nodes connected to that task. This allows us to store the time taken to reach each task.<\/p>\n
for node in topo_order:\n for neighbor, duration in graph[node]:\n completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)\n\n # The maximum time required to complete all tasks\n return max(completion_time)\n<\/code><\/pre>\n4. Writing the Complete Code<\/h3>\n
We will write the final code by integrating all the steps together.<\/p>\n
def critical_path(n, edges):\n graph = defaultdict(list)\n in_degree = [0] * (n + 1)\n completion_time = [0] * (n + 1)\n\n # Construct the graph and calculate in-degrees\n for u, v, w in edges:\n graph[u].append((v, w))\n in_degree[v] += 1\n\n # Perform topological sort\n zero_degree_queue = []\n for i in range(1, n + 1):\n if in_degree[i] == 0:\n zero_degree_queue.append(i)\n \n topo_order = []\n while zero_degree_queue:\n node = zero_degree_queue.pop(0)\n topo_order.append(node)\n for neighbor, duration in graph[node]:\n in_degree[neighbor] -= 1\n if in_degree[neighbor] == 0:\n zero_degree_queue.append(neighbor)\n\n # Calculate the completion time for each task\n for node in topo_order:\n for neighbor, duration in graph[node]:\n completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)\n\n # The maximum time required to complete all tasks\n return max(completion_time)\n\n# Example execution\nif __name__ == \"__main__\":\n n = 5\n edges = [\n (1, 2, 3),\n (1, 3, 2),\n (2, 4, 4),\n (3, 4, 5),\n (4, 5, 1)\n ]\n result = critical_path(n, edges)\n print(\"Length of the critical path:\", result)\n<\/code><\/pre>\nConclusion<\/h2>\n
In this lecture, we learned how to find the critical path. By using graph theory and topological sorting, we safely processed each task and calculated the time taken for each task to derive the critical path. This approach can ultimately be applied to various project management and scheduling problems.<\/p>\n
Moreover, in practical applications, such algorithms form the basis of complex project management and will significantly aid in enhancing efficiency. I hope you continue to improve your programming skills by tackling various algorithm problems in the future.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"