算法描述 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
using namespace std;
int list[MAXN][MAXN][2]; // 链接表存储图 int seq[MAXN]; // 拓扑排序后的节点序列 int deg[MAXN]; // 出度 int d[MAXN]; // int trace[MAXN]; int n;
void initialize_single_source() { for(int i=1;i<=n;i++) d[i]=INF; d[1]=0; }
// 对无环图DAG拓扑排序 void topologic_sort() { 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++) { for(j=0;j<deg[i];j++) { indeg[list[i][j][0]]++; } } /**//* for(i=1;i<=n;i++) printf("%d ",indeg[i]); printf("\n"); */ for(i=0;i<n;i++) { for(j=1;j<=n;j++) { if(indeg[j]==0 && visit[j]==0) { 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"); }
void relax(int i,int j) { if(d[list[i][j][0]]>d[i]+list[i][j][1]) { trace[list[i][j][0]]=i; d[list[i][j][0]]=d[i]+list[i][j][1]; } }
void shortest_path_DAG() { int i,j,k; for(i=0;i<n;i++) { int v=seq[i]; for(j=0;j<deg[v];j++) { relax(v,j); } } for(i=1;i<=n;i++) printf("%d distance:%d\n",trace[i],d[i]); }
void readdata() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",°[i]); for(j=0;j<deg[i];j++) scanf("%d%d",&list[i][j][0],&list[i][j][1]); } }
int main() { freopen("test.txt","r",stdin); readdata(); topologic_sort(); initialize_single_source(); shortest_path_DAG(); return 1; }
|