NeFut Logo NeFut
中 Admin Login

In-Depth Analysis of Topological Sorting and Critical Path Algorithms

Published at: 2026-05-27 09:17 Last updated: 2026-06-06 13:04
#algorithm #C++ #Graph

Core Logic and Mathematical Principles

Topological sorting plays a crucial algebraic role in solving the Critical Path Method (CPM) problem and project scheduling. In a directed acyclic graph (DAG) with edge weights, the edge weights typically represent the time required to complete a subtask, while the vertices in the graph represent "events" at certain stages of the project.

To accurately identify which tasks are "critical tasks" (i.e., tasks that have no tolerance for delays and will directly cause the entire project duration to be extended if delayed), we need to bi-directionally drive the following four core algebraic states in the topological space:

1. Earliest Event Time $ve[i]$ (Forward Pass)

$$ve[i] = \text{max}_{(u, i) \in E} \{ ve[u] + w(u, i) \}$$

The shortest total duration of the entire project is strictly equal to the $ve$ value at the sink (end) node.

2. Latest Event Time $vl[i]$ (Backward Pass)

$$vl[i] = \text{min}_{(i, v) \in E} \{ vl[v] - w(i, v) \}$$

3. Activity (Edge) Time Slack State Extraction

Once the vertex states have been bi-directionally refined through topological processing, we can shift our focus to specific activities (edges $e = (u, v)$, with weight $w$):

$$\Delta e = el[e] - ee[e] = vl[v] - ve[u] - w$$

4. Algebraic Criterion for Critical Path

If an edge (activity) satisfies $ \Delta e == 0$** (i.e., $vl[v] - ve[u] - w == 0$), then this activity is termed a critical activity. Critical activities have no slack. The complete path formed by a series of critical activities from the source to the sink is called the critical path**. There can be multiple parallel critical paths in a project DAG.

Algorithm Derivation and State Design

1. Dual Topological Stack Control

  1. First, run the standard Kahn's topological sorting algorithm. When nodes are dequeued, push them into an auxiliary stack reverse_order.
  2. Once the topological sorting is complete, the order from the top to the bottom of the reverse_order stack naturally constitutes the reverse topological order of the graph.
  3. Use the forward topological order to recursively compute the full set of ve[i].
  4. Pop the reverse_order stack and use the reverse topological order to recursively compute the full set of vl[i].

C++ Standard Source Code (Critical Path Core Extraction Template)

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, weight;
};

std::vector<Edge> adj[MAXN];
int in_degree[MAXN];
int ve[MAXN]; // Earliest Event Time
int vl[MAXN]; // Latest Event Time

std::vector<int> topo_order;   // Forward Topological Order
std::stack<int> reverse_order; // Reverse Topological Order

bool find_critical_path(int n) {
    std::queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
        ve[i] = 0; // Initialize earliest time base to 0
    }

    // 1. Forward Topological Drive: Relax ve states
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        reverse_order.push(u); // Push into reverse order stack

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            int w = adj[u][i].weight;

            // State transition: take the longest time from preceding dependencies
            if (ve[u] + w > ve[v]) {
                ve[v] = ve[u] + w;
            }

            if (--in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    // Cycle safety check
    if (topo_order.size() != static_cast<size_t>(n)) return false;

    // Find the total project duration (maximum earliest time point)
    int total_project_time = 0;
    for (int i = 1; i <= n; ++i) {
        total_project_time = std::max(total_project_time, ve[i]);
    }

    // 2. Initialize reverse boundary: set the latest occurrence time of all sinks to total project time
    for (int i = 1; i <= n; ++i) {
        vl[i] = total_project_time; 
    }

    // 3. Reverse Topological Drive: Backtrack vl states
    while (!reverse_order.empty()) {
        int u = reverse_order.top();
        reverse_order.pop();

        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            int w = adj[u][i].weight;

            // Reverse state transition: subsequent constraints approach from the back
            if (vl[v] - w < vl[u]) {
                vl[u] = vl[v] - w;
            }
        }
    }

    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    if (!(std::cin >> n >> m)) return 0;

    std::vector<Edge> all_edges;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{u, v, w});
        all_edges.push_back(Edge{u, v, w});
        in_degree[v]++;
    }

    if (!find_critical_path(n)) {
        std::cout << "Graph contains cycles, no critical path exists.\n";
        return 0;
    }

    std::cout << "Total Project Duration: " << ve[topo_order.back()] << "\n";
    std::cout << "Critical Activities (Edges):\n";

    // 4. Traverse all activities to extract critical activities through algebraic criteria
    for (size_t i = 0; i < all_edges.size(); ++i) {
        int u = all_edges[i].from;
        int v = all_edges[i].to;
        int w = all_edges[i].weight;

        // Core algebraic criterion: vl[v] - ve[u] - w == 0
        if (vl[v] - ve[u] - w == 0) {
            std::cout << u << " -> " << v << " (weight: " << w << ")\n";
        }
    }

    return 0;
}

NOIP Practical Pitfall Guide

  1. Pollution of vl initial boundaries in graphs with multiple source or sink nodes: If the project graph has multiple sink nodes with no outgoing edges, some contestants may hastily write vl[n] = ve[n]. This is correct in a single-sink graph. However, in a multi-sink graph, only some of the vl values are correctly constrained, while others will remain at their initial 0 or incorrect large integer values. During the reverse topological backtracking, these erroneous boundary values will instantly pollute the entire graph's vl state, leading to a completely disordered critical path calculation.
  1. Misunderstanding that "nodes where $ve[i] == vl[i]$ are connected by critical activities": This is a classic theoretical high-frequency error point. In certain special topological structures, there may exist two points $u$ and $v$ that both satisfy $ve[u] == vl[u]$ and $ve[v] == vl[v}$, but the edge weight $w$ connecting them is small, leading to $vl[v] - ve[u] - w > 0$. This means that this edge itself has slack time and is not a critical activity. Iron Law: To determine the critical path, one must strictly apply the algebraic criterion of $vl[v] - ve[u] - w == 0$ to the edges (activities), and not just perform equality checks on the endpoints.

Classic NOIP/Luogu Problems

1. Luogu P1113 Miscellaneous Tasks

2. Luogu P1821 [USACO07MAR] Cow Party

  1. Forward Drive: Directly run Dijkstra's algorithm once on the original graph with $X$ as the source point, the resulting $dist[i]$ will be the shortest path for each cow to return to their own farm from the party.
  2. Backward Drive: Reverse the direction of all directed edges in the original graph (establish a reverse graph) and run Dijkstra's algorithm again with $X$ as the source point. Due to the edge weight inversion, the resulting $dist'[i]$ essentially becomes the shortest path for each city to go to $X$ in the original graph. Adding the two parts of time $dist[i] + dist'[i]$ can extract the complete lifecycle cost for each cow. This symmetry of "forward calculation, backward constraint" constitutes the core foundation of complex graph state design.
Original Source: local://12.3
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS