1、基本算法
我们知道DAG上一定存在拓扑排序，且若在有向图G中从顶点Vi->Vj有一条路径，则在拓扑排序中顶点Vi一定在顶点Vj之前，而因为在DAG图中没有环，所以按照DAG图的拓扑排序进行序列最短路径的更新，一定能求出最短路径。即使存在权重为负的边,但是它是有向无环图,所以它一定不存在权重为负的环,所以一定可以求出最短路径。
2、基本步骤
处理顶点V时，对每条离开的边<u,v>执行松弛运算。若果<u,v>给出从源点到v的一条最短路径（经过u），则更新到v的最短路径。这个过程将检查图中每个顶点的所有路径，同时，拓扑排序确保按正确的顺序处理顶点。
3、正确性验证
如果有向无环图包含从结点u到结点v的最短路径,则u在拓扑排序中一定位于v的前面。我们只需要按照拓扑排序的次序对结点进行一次遍历处理即可。每次对一个结点进行处理时,我们对该结点出发的所有的边进行松弛操作。
4、时间复杂度:
拓扑排序为O( V + E ),松弛操作那部分的代码的时间复杂度为O( V + E ),所以时间复杂度为O( V + E )
伪代码：
（1）初始化，源点的d值为0，其他的节点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);
}
}
