[理学]dijsktra模板最短路径

《[理学]dijsktra模板最短路径》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、intdist[maxnum];//表示当前点到源点的最短路径长度intprev[maxnum];//记录当前点的前一个结点intc[maxnum][maxnum];//记录图的两点间路径长度intn,line;//图的结点数和路径数 voidDijkstra(intn,intv,int*dist,int*prev,intc[maxnum][maxnum]){bools[maxnum];//判断是否已存入该点到S集合中for(inti=1;i<=n;++i){dist[i]=c[v][i];s[i]=0;/

2、/初始都未用过该点if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[v]=1; //依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中//一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度for(inti=2;i<=n;++i){inttmp=maxint;intu=v;//找出当前未使用的点j的dist[j]最小值for(intj=1;j<=n;++j)if((!s[j])&&dist[j]

3、p){u=j;//u保存当前邻接点中距离最小的点的号码tmp=dist[j];}s[u]=1;//表示u点已存入S集合中 //更新distfor(intj=1;j<=n;++j)if((!s[j])&&c[u][j]

4、e[tot]=u;tot++;inttmp=prev[u];while(tmp!=v){que[tot]=tmp;tot++;tmp=prev[tmp];}que[tot]=v;for(inti=tot;i>=1;--i)if(i!=1)cout<";elsecout<>n;//输入路径数cin>>line;intp,q,l

5、en;//输入p,q两点及其路径长度 //初始化c[][]为maxintfor(inti=1;i<=n;++i)for(intj=1;j<=n;++j)c[i][j]=maxint; for(inti=1;i<=line;++i){cin>>p>>q>>len;if(len

6、or(intj=1;j<=n;++j)printf("%8d",c[i][j]);printf("");} Dijkstra(n,1,dist,prev,c); //最短路径长度cout<<"源点到最后一个顶点的最短路径长度:"<