C++代码ShortestPath_Floyd

最短路径算法 Status ShortestPath_Floyd(Graph &G,Distance &D,Path &P,Number &N) {int i,j,k; int s,t; if(G.kind==DG||G.kind==UDG) return ERROR; for(j=0;j<G.vexnum;j++) for(k=0;k<G.vexnum;k++) {D[j][k]=G.arcs[j][k]; P[j][k][0]=j; P[j][k][1]=k; N[j][k]=2; } for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) for(k=0;k<G.vexnum;k++) if(D[j][i]+D[i][k]<D[j][k]) {D[j][k]=D[j][i]+D[i][k]; for(s=0,t=0;s<=N[j][i]-1;s++,t++) P[j][k][t]=P[j][i][s]; for(s=1;s<=N[i][k]-1;s++,t++) P[j][k][t]=P[i][k][s]; N[j][k]=N[j][i]+N[i][k]-1; } return OK; }