1、基本算法
我們知道DAG上一定存在拓撲排序，且若在有向圖G中從頂點Vi->Vj有一條路徑，則在拓撲排序中頂點Vi一定在頂點Vj之前，而因為在DAG圖中沒有環(huán)，所以按照DAG圖的拓撲排序進行序列最短路徑的更新，一定能求出最短路徑。即使存在權重為負的邊,但是它是有向無環(huán)圖,所以它一定不存在權重為負的環(huán),所以一定可以求出最短路徑。
2、基本步驟
處理頂點V時，對每條離開的邊<u,v>執(zhí)行松弛運算。若果<u,v>給出從源點到v的一條最短路徑（經過u），則更新到v的最短路徑。這個過程將檢查圖中每個頂點的所有路徑，同時，拓撲排序確保按正確的順序處理頂點。
3、正確性驗證
如果有向無環(huán)圖包含從結點u到結點v的最短路徑,則u在拓撲排序中一定位于v的前面。我們只需要按照拓撲排序的次序對結點進行一次遍歷處理即可。每次對一個結點進行處理時,我們對該結點出發(fā)的所有的邊進行松弛操作。
4、時間復雜度:
拓撲排序為O( V + E ),松弛操作那部分的代碼的時間復雜度為O( V + E ),所以時間復雜度為O( V + E )
偽代碼：
（1）初始化，源點的d值為0，其他的節(jié)點d值為INF。
（2）對DAG進行拓撲排序，得到拓撲序列。
（3）按照拓撲序列遍歷DAG的點，對于每個點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
題意:
給定一個DAG,求入度為0的點到出度為0的點的最長路徑
題解:

#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);
    }
}