python coding test course, finding critical path

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.

Problem Definition

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.

Problem Description

Input:
- n (1 ≤ n ≤ 100): Number of tasks
- edges: A list representing the dependency relationships between tasks, where each element is a tuple (u, v, w), 
  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.

Output:
- The longest time required to complete all tasks (length of the critical path)

Example Input

n = 5
edges = [
    (1, 2, 3),
    (1, 3, 2),
    (2, 4, 4),
    (3, 4, 5),
    (4, 5, 1)
]

Example Output

8

Problem Solving and Approach

To solve this problem, we can implement it by following these steps.

1. Representing the Directed Graph

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.

from collections import defaultdict
import sys

def critical_path(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    completion_time = [0] * (n + 1)

    # Construct the graph and calculate in-degrees
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1

2. Topological Sorting

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.

    # Perform topological sort
    zero_degree_queue = []
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            zero_degree_queue.append(i)
    
    topo_order = []
    while zero_degree_queue:
        node = zero_degree_queue.pop(0)
        topo_order.append(node)
        for neighbor, duration in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                zero_degree_queue.append(neighbor)

3. Calculating Minimum Duration

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.

    for node in topo_order:
        for neighbor, duration in graph[node]:
            completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)

    # The maximum time required to complete all tasks
    return max(completion_time)

4. Writing the Complete Code

We will write the final code by integrating all the steps together.

def critical_path(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * (n + 1)
    completion_time = [0] * (n + 1)

    # Construct the graph and calculate in-degrees
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1

    # Perform topological sort
    zero_degree_queue = []
    for i in range(1, n + 1):
        if in_degree[i] == 0:
            zero_degree_queue.append(i)
    
    topo_order = []
    while zero_degree_queue:
        node = zero_degree_queue.pop(0)
        topo_order.append(node)
        for neighbor, duration in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                zero_degree_queue.append(neighbor)

    # Calculate the completion time for each task
    for node in topo_order:
        for neighbor, duration in graph[node]:
            completion_time[neighbor] = max(completion_time[neighbor], completion_time[node] + duration)

    # The maximum time required to complete all tasks
    return max(completion_time)

# Example execution
if __name__ == "__main__":
    n = 5
    edges = [
        (1, 2, 3),
        (1, 3, 2),
        (2, 4, 4),
        (3, 4, 5),
        (4, 5, 1)
    ]
    result = critical_path(n, edges)
    print("Length of the critical path:", result)

Conclusion

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.

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.