最小代价算法编程.doc

最小代价算法编程【实验目的】?加深对最小代价算法的理解;?能够使用C语言(或者Matlab)实现最小代价算法并给出路由表;?掌握Dijkstra算法的原理。【实验内容】?使用C语言(或者Matlab)针对给出的网络拓扑图使用Dijkstra算法计算最小代价路径,并给出路由器路由表;【实验设备】?一台PC机【实验步骤】针对下图给出的网络拓扑图,计算Node3至其它各节点的最小代价路径,并给出Node3的路由表。实验代码:本代码需要在本地的txt文档中录入图的邻接矩阵#include<>#include<>#defineINF0x7fffffff#definemaxN50intmatrix[maxN][maxN];intMinIndex[maxN];intMinIndex2[maxN];charPath[500];intn;voidDijkstra(intout[],intN,intv0,intn){inti,j;intvisited[maxN]={0};intlast_visited=0;intmatrix_2[maxN][maxN];intmatrix_3[maxN][maxN];//将默认以A点为起点的矩阵转化为以要查询的点为起点的矩阵//行变化for(i=0;i<N;i++){for(j=0;j<N;j++){matrix_2[i][j]=matrix[i][j];}}for(i=0,j=0;j<N;j++){matrix[i][j]=matrix_2[i+n][j];}for(i=0;i<N;i++){while(i==n)break;for(j=0;j<N;j++){matrix[i+1][j]=matrix_2[i][j];}}for(i=0;i<N;i++){for(j=0;j<N;j++){matrix[i+n+1][j]=matrix_2[i+n+1][j];}while(i+n+2==N)break;}//列变化for(i=0;i<N;i++){for(j=0;j<N;j++){matrix_3[i][j]=matrix[i][j];}}for(i=1;i<N;i++){for(j=0;j<N;j++){matrix[i][j]=matrix_3[i][j+n];}}for(i=1;i<N;i++){matrix[i][0]=matrix_3[i][n];}for(j=0;j<N;j++){while(j==n)break;for(i=0;i<N;i++){matrix[i][j+1]=matrix_3[i][j];}}for(j=0;j<N;j++){for(i=0;i<N;i++){matrix[i][j+n+1]=matrix_3[i][j+n+1];}while(j+n+2==N)break;}for(i=0;i<N;i++){out[i]=INF;}visited[v0]=1;out[v0]=0;for(i=0;i<N-1;i++){//遍历定点周围的其他所有点for(j=0;j<N;j++){if(visited[j]==0){if(matrix[v0][j]!=0){intdist=matrix[v0][j]+last_visited;if(dist<out[j]){out[j]=dist;}}}}//找出最小值intminIndex=0;while(visited[minIndex]==1){minIndex++;}for(j=minIndex;j<N;j++){if(visited[j]==0&&out[j]<out[minIndex]){minIndex=j;}}last_visited=out[minIndex];visited[minIndex]=1;v0=minIndex;MinIndex[i+1]=minIndex;MinIndex2[i+1]=minIndex;}//生成路径图for(i=0;i<N;i++){if(MinIndex2[i]==0)MinIndex2[i]=n;elseif(MinIndex2[i]<=n)MinIndex2[i]=MinIndex2[i]-1;}intp,q,m=0;for(i=N-1;i>0;i--){p=N-i;q=N-i-1;Path[m]=(char)(MinIndex2[i]%10+'A');m++;for(j=0;j<i;j++){if(matrix[MinIndex[N-1-p]][MinIndex[N-1-q]]!=0){Path[m]='>';m++;Path[m]='-';m++;Path[m]=(char)(MinIndex2[N-1-p]%10+'A');m++;p++;q++;if((p-q