时间复杂度

因为只需要依次遍历这n个顶点更新最短距离, 所以时间复杂度是线性的. O(n)

模板

int d[N]; // 存储每个节点的入度数
void topsort()
{
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0;

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q.push(i);

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for(int i = h[t] ; i != -1 ; i ++ )
        {
            int j = e[i];
            if(dis[j] > dis[t] + w[i])
                dis[j] = dis[t] + w[i];

            d[j] -- ; // 入度 - 1
            if(!d[j]) q.push(j);
        }
    }
}

例题