算法描述 topologically_sort() initialize_single_source() for each vertex v, taken in topologically sorted order do for each edge (v,u) do relax(v,u) end
// shortest single source path on DAG
#include <iostream>
#define MAXN 200
#define INF 0xfffffff
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int list[MAXN][MAXN][2]; // 链接表存储图
int seq[MAXN]; // 拓扑排序后的节点序列
int deg[MAXN]; // 出度
int d[MAXN]; //
int trace[MAXN];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void initialize_single_source()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
for(int i=1;i<=n;i++)
d[i]=INF;
d[1]=0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 对无环图DAG拓扑排序
void topologic_sort()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j,k,indeg[MAXN],visit[MAXN];
//for(i=1;i<=n;i++) degree[i]=deg[i];
for(i=1;i<=n;i++) indeg[i]=0,visit[i]=0;
// 求所有节点的入度
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=0;j<deg[i];j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
indeg[list[i][j][0]]++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//*
for(i=1;i<=n;i++) printf("%d ",indeg[i]);
printf("\n");
*/
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(indeg[j]==0 && visit[j]==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
visit[j]=1;
seq[i]=j;
for(k=0;k<deg[j];k++) indeg[list[j][k][0]]--;
break;
}
}
}
for(i=1;i<=n;i++) printf("%d \n",indeg[i]);
printf("\n");
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void relax(int i,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(d[list[i][j][0]]>d[i]+list[i][j][1])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
trace[list[i][j][0]]=i;
d[list[i][j][0]]=d[i]+list[i][j][1];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void shortest_path_DAG()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j,k;
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int v=seq[i];
for(j=0;j<deg[v];j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
relax(v,j);
}
}
for(i=1;i<=n;i++) printf("%d distance:%d\n",trace[i],d[i]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void readdata()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d",°[i]);
for(j=0;j<deg[i];j++) scanf("%d%d",&list[i][j][0],&list[i][j][1]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
freopen("test.txt","r",stdin);
readdata();
topologic_sort();
initialize_single_source();
shortest_path_DAG();
return 1;
}
|