学步园

1.将网拓扑排序

2.进行关键路径算法：采用动态规划的思想每次选择路程长的边作为结果更新dist[]数组。

算法实现：

void toposort()//找出其中一个序列<br /> {<br /> int cnt=0, mm=0;<br /> for(int i=0;i<nnum;i++)<br /> if(indegree[i]==0) Queue[cnt]=i, dist[cnt]=0, cnt++;<br /> while(cnt<nnum)<br /> {<br /> edge *head=next_edge[Queue[mm]];<br /> mm++;<br /> while(head!=NULL)<br /> {<br /> indegree[head->to]--;<br /> if(indegree[head->to]==0) Queue[cnt]=head->to, cnt++;<br /> head=head->next;<br /> }<br /> }<br /> //for(int i=0;i<nnum;i++) printf("%d ",Queue[i]); printf("/n");<br /> }</p> <p>//每次将顶点取出采用动态规划的思想依次求解每个点的最长距离<br /> int keypath()<br /> {<br /> int front=0,sumnum;<br /> while(true)<br /> {<br /> int cur=Queue[front];<br /> if(front==nnum-1) return sumnum;<br /> edge *head=next_edge[cur];<br /> while(head!=NULL)<br /> {<br /> int curnum=head->to;<br /> if(dist[curnum]<dist[cur]+head->cost)<br /> dist[curnum]=dist[cur]+head->cost;<br /> sumnum=dist[curnum];<br /> head=head->next;<br /> }<br /> front++;<br /> }<br /> }