1签舞、基本算法
我們知道DAG上一定存在拓?fù)渑判颍胰粼谟邢驁DG中從頂點Vi->Vj有一條路徑槽袄，則在拓?fù)渑判蛑许旤cVi一定在頂點Vj之前给僵，而因為在DAG圖中沒有環(huán)毫捣，所以按照DAG圖的拓?fù)渑判蜻M(jìn)行序列最短路徑的更新，一定能求出最短路徑帝际。即使存在權(quán)重為負(fù)的邊,但是它是有向無環(huán)圖,所以它一定不存在權(quán)重為負(fù)的環(huán),所以一定可以求出最短路徑蔓同。
2、基本步驟
處理頂點V時蹲诀，對每條離開的邊<u,v>執(zhí)行松弛運算斑粱。若果<u,v>給出從源點到v的一條最短路徑（經(jīng)過u），則更新到v的最短路徑脯爪。這個過程將檢查圖中每個頂點的所有路徑则北，同時，拓?fù)渑判虼_保按正確的順序處理頂點痕慢。
3尚揣、正確性驗證
如果有向無環(huán)圖包含從結(jié)點u到結(jié)點v的最短路徑,則u在拓?fù)渑判蛑幸欢ㄎ挥趘的前面。我們只需要按照拓?fù)渑判虻拇涡驅(qū)Y(jié)點進(jìn)行一次遍歷處理即可掖举。每次對一個結(jié)點進(jìn)行處理時,我們對該結(jié)點出發(fā)的所有的邊進(jìn)行松弛操作快骗。
4、時間復(fù)雜度:
拓?fù)渑判驗镺( V + E ),松弛操作那部分的代碼的時間復(fù)雜度為O( V + E ),所以時間復(fù)雜度為O( V + E )
偽代碼：
（1）初始化塔次，源點的d值為0方篮，其他的節(jié)點d值為INF。
（2）對DAG進(jìn)行拓?fù)渑判蚶海玫酵負(fù)湫蛄小?br>
（3）按照拓?fù)湫蛄斜闅vDAG的點藕溅，對于每個點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);
}
}
