最小路集的计算机解法

最小路集的计算机解法1.问题描述设G是有n个节点的有向网络。对无向网络可以看成是双向的，故无向网络亦可化为有向网络。假定节点之间无并联弧，输入节点为I，输出节点为L，如何找出I、L之间的所有最小路集。2.算法思想整个算法的基本思想可描述如下：输入节点I作为起始节点；由起始节点出发，依次选下一步可达的节点i；判断所选节点i是否走过。若是，则退回起始节点，转（2）；判断是否已达到输出节点L。若否，则把i作为起始节点，转（2）；判断是否已找到了所有最小路集。如否，则把上节点作为起始节点，转（2）；结束。由此可见，算法的关键是需要进行三个判断：一是判断节点是否与前面走过的节点重复，二是判断是否找到了一条最小路集，三是判断是否找到了所有最小路集。3.算法参数和符号n：网络中节点数；I：输入节点标号；L：输出节点标号；E：扇出向量；E=（E（1），…，E（i），…，E（n）），表示离开节点1，…，n的弧数。其中E（i）表示节点i下一步可以到达的节点有E(i)个。E阵完全由网络所确定。R：路线矩阵；R=（r(i,k)），i=1，…，n；k=；，…，E（i）。R的第i行记录了节点i可以一步到达的节点标号。R不一定是长方阵，即对不同的行，列数未必相同。为了表示i的下一步的节点已经完全走遍，同时区分出输入节点I，在R的每行再增加一个元素r(I,E(i)+1)，当i≠I时，取-1，当i=I时，取0。此时仍称R为G路线矩阵。显然，R阵完全由网络所确定。C：位置向量；C=（C(1)，…，C(i)，…，C(n)），其中C（j）记录节点j在R中的列号。而元素r(j,Cj)记录j下一步到达的节点标号。F：检验向量；F为定义在节点{1，2，…，n}上的函数，初值为i≠I时，取1，i=L时取-1,其余情况取0。F的作用为：当某个节点j已走过时，F（j）的值就为1。在寻找一条最小路集的过程中，这可以用来判断后面的节点是否与已走过的节点有重复。一旦F（j）=1，表明已达到输出节点L，即找到了一条最小路集。P：输出矩阵；所有最小路集组成的矩阵，其中每一列为由输入节点I到输出节点L的一条最小路集。P的元素P(v,w)记录了第w条最小路集中第v个节点的标号。用tc2.0编写代码如下：#includestdio.hmain(){intn,I,L,i,j,w,v;intE[20],C[20],F[20],U[20];intR[20][20],P[20][20];for(i=0;in;i++)for(j=0;jn;j++)P[i][j]=0;for(i=0;in;i++)for(j=0;jn;j++)R[i][j]=0;printf(pleaseEntertheelementn,I,L:);scanf(%d,%d,%d,&n,&I,&L);printf(pleaseEnterthe1DArryE:);for(i=0;in;i++)scanf(%d,&E[i]);printf(pleaseEnterthe2DArryR:);for(i=0;in;i++){for(j=0;jE[i];j++)scanf(%d,&R[i][j]);}for(i=0;in;i++){C[i]=1;}j=I;P[0][0]=I;w=1;v=2;for(i=0;in;i++){if(i==I-1)R[i][E[i]]=-1;elseR[i][E[i]]=0;}for(i=0;in;i++){if(i==I-1)F[i]=1;elseif(i==L-1)F[i]=-1;elseF[i]=0;}A:P[v-1][w-1]=R[j-1][C[j-1]-1];{if(R[j-1][C[j-1]-1]0){if(F[R[j-1][C[j-1]-1]-1]0){C[j-1]=C[j-1]+1;gotoA;}else{if(F[R[j-1][C[j-1]-1]-1]==0){j=P[v-1][w-1];F[j-1]=1;v=v+1;gotoA;}else{U[w-1]=v;C[j-1]=C[j-1]+1;{for(i=1;i=U[w-1]-1;i++)P[i-1][w]=P[i-1][w-1];}w=w+1;gotoA;}}}else{if(R[j-1][C[j-1]-1]==0){F[j-1]=0;C[j-1]=1;j=P[v-3][w-1];C[j-1]=C[j-1]+1;v=v-1;gotoA;}else{printf(theresultis:\n);for(i=0;iw-1;i++){{for(j=0;jU[i];j++)printf(%d\t,P[j][i]);}printf(\n);}}}}}操作：执行dengshihui.exe文件或在turboc环境下运行dengshihui.cpp文件，按要求输入合理的数据，便得出路集的矩阵（二维数组）。如：在turboc环境下运行dengshihui.cpp，图如下操作：ctrl+F9输入n,I,L，拿，I=4，L=6输入一维数组E输入二维数组R：回车ALT+F5找到一条最小路集。其他的例子：注：如果节点数大于20，需要到源程序中修改一维，二维数组的维数。