1、基本算法
我們知道DAG上一定存在拓?fù)渑判颍胰粼谟邢驁DG中從頂點(diǎn)Vi->Vj有一條路徑，則在拓?fù)渑判蛑许旤c(diǎn)Vi一定在頂點(diǎn)Vj之前，而因?yàn)樵贒AG圖中沒有環(huán)，所以按照DAG圖的拓?fù)渑判蜻M(jìn)行序列最短路徑的更新，一定能求出最短路徑。即使存在權(quán)重為負(fù)的邊,但是它是有向無(wú)環(huán)圖,所以它一定不存在權(quán)重為負(fù)的環(huán),所以一定可以求出最短路徑。
2、基本步驟
處理頂點(diǎn)V時(shí)，對(duì)每條離開的邊<u,v>執(zhí)行松弛運(yùn)算。若果<u,v>給出從源點(diǎn)到v的一條最短路徑（經(jīng)過(guò)u），則更新到v的最短路徑。這個(gè)過(guò)程將檢查圖中每個(gè)頂點(diǎn)的所有路徑，同時(shí)，拓?fù)渑判虼_保按正確的順序處理頂點(diǎn)。
3、正確性驗(yàn)證
如果有向無(wú)環(huán)圖包含從結(jié)點(diǎn)u到結(jié)點(diǎn)v的最短路徑,則u在拓?fù)渑判蛑幸欢ㄎ挥趘的前面。我們只需要按照拓?fù)渑判虻拇涡驅(qū)Y(jié)點(diǎn)進(jìn)行一次遍歷處理即可。每次對(duì)一個(gè)結(jié)點(diǎn)進(jìn)行處理時(shí),我們對(duì)該結(jié)點(diǎn)出發(fā)的所有的邊進(jìn)行松弛操作。
4、時(shí)間復(fù)雜度:
拓?fù)渑判驗(yàn)镺( V + E ),松弛操作那部分的代碼的時(shí)間復(fù)雜度為O( V + E ),所以時(shí)間復(fù)雜度為O( V + E )
偽代碼：
（1）初始化，源點(diǎn)的d值為0，其他的節(jié)點(diǎn)d值為INF。
（2）對(duì)DAG進(jìn)行拓?fù)渑判?，得到拓?fù)湫蛄小?br> （3）按照拓?fù)湫蛄斜闅vDAG的點(diǎn)，對(duì)于每個(gè)點(diǎn)u，遍歷其所有的出邊<u,v>，如果d[v] > d[u] + length<u,v>，則更新。

#include <cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXE=1000010;
const int MAXN=100010;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,val,next;
};
Node edge[MAXE];
int head[MAXN];
queue<int> result;
int in[MAXN];
int dis[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].val=val;
    head[u]=cnt++;
}
void topoSort(int n)
{
    queue<int> zero;
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0) zero.push(i);
    }
    while(!zero.empty())
    {
        int u=zero.front();
        zero.pop();
        result.push(u);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            in[v]--;
            if(in[v]==0) zero.push(v);
        }
    }
}
void DAGShortestPath(int st,int n)
{
    topoSort(n);
    memset(dis,INF,sizeof(dis));
    dis[st]=0;
    while(!result.empty())
    {
        int u=result.front();
        result.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==INF) printf("INF\n");
        else printf("%d\n",dis[i]);
    }
}
int main()
{
    int n,m,a,b,val,st;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        scanf("%d",&st);
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&val);
            addEdge(a,b,val);
            in[b]++;
        }
        DAGShortestPath(st,n);
    }
}

Test for Job
題意:
給定一個(gè)DAG,求入度為0的點(diǎn)到出度為0的點(diǎn)的最長(zhǎng)路徑
題解:

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
const int MAXE=1000010;
const int MAXN=100010;
const long long INF=-0x7fffffffffffffff;
struct Node
{
    int to,val,next;
};
Node edge[MAXE];
int head[MAXN];
queue<int> result;
int in[MAXN];
int out[MAXN];
long long dis[MAXN];
int weight[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].val=val;
    head[u]=cnt++;
}
void topoSort(int n)
{
    queue<int> zero;
    for(int i=0;i<=n;i++)
    {
        if(in[i]==0) zero.push(i);
    }
    while(!zero.empty())
    {
        int u=zero.front();
        zero.pop();
        result.push(u);
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            in[edge[i].to]--;
            if(in[edge[i].to]==0) zero.push(edge[i].to);
        }
    }
}
void DAGShortestPath(int st,int n)
{
    topoSort(n);
    for(int i=0;i<=n;i++) dis[i]=INF;
    dis[st]=0;
    while(!result.empty())
    {
        int u=result.front();
        result.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]<dis[u]+edge[i].val)
            {
                dis[v]=dis[u]+edge[i].val;
            }
        }
    }
    long long ans=INF;
    for(int i=0;i<=n;i++)
    {
        if(out[i]==0) ans=max(ans,dis[i]);
    }
    printf("%lld\n",ans);
}
int main()
{
    int n,m,a,b,val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&weight[i]);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a,b,weight[b]);
            in[b]++;
            out[a]++;
        }
        for(int i=1;i<=n;i++)
        {
            if(in[i]==0)
            {
                addEdge(0,i,weight[i]);
                in[i]++;
                out[0]++;
            }
        }
        DAGShortestPath(0,n);
    }
}