suanfa.txt

算法实现单元点最短路径问题

#include<stdio.h>
int num;
int s[8],dist[8];
int d[8][8];
int cost[8][8]={{0,0,0,0,0,0,0,0},
{0,0,20,50,30,1000,1000,1000},
{0,1000,0,25,1000,1000,70,1000},
{0,1000,1000,0,40,25,50,1000},
{0,1000,1000,1000,0,55,1000,1000},
{0,1000,1000,1000,1000,0,10,70},
{0,1000,1000,1000,1000,1000,0,50},
{0,1000,1000,1000,1000,1000,1000,0}};
void init(){
     
     int i=0,j=0;
     for(i=1;i<=7;i++){                                
     for(j=1;j<=7;j++){
   d[i][j]=1;                   
      }    
     s[i]=0;                                        /*表示第i个接点没有找到最短路径*/
     dist[i]=cost[1][i];
 }
} 
void find(){
     int k=0;
     int i=0;
     int j=0;
     int m=0;
  s[1]=1;
  dist[1]=0;
  for(k=2;k<=7;k++){
  for(num=2000,i=2;i<=7;i++){              /*NUM便于每次开始时候都能比较*/
   if(s[i]==0)                          /*在还没有找到最短路径的接点中找距离最近的接点*/
    if(dist[i]<=num){
     num=dist[i];
     j=i;                         /*用J记录距离最近的接点*/ 
    }
  }
  s[j]=1;                                   
  for(m=2;m<=7;m++){                         /*将已经找到的点加入记录其路径的数组*/
   if(d[j][m]==1){
    d[j][m]=j;
       break;
   }
  }
  for(i=2;i<=7;i++){                         
   if(s[i]==0){
    if(dist[i]>dist[j]+cost[j][i]){     /*每找到一个新接点如果其他最短路径要修改，则改变他们的路径长，以及其路径*/
     dist[i]=dist[j]+cost[j][i];       /*修改到已经找到的集合的最短距离*/
     for(m=2;m<=7;m++)               /*修改其路径*/
d[i][m]=d[j][m];            /*路径改为刚找到的接点的路径*/
    }
   }
  }
 }
 }  
          
          
void print(){
        int i=0;
        int j=0;
      for(i=1;i<=7;i++){                               /*输出其路径长，路径*/
  printf("%d:  %d",i,dist[i]);
  for(j=1;j<=7;j++){
   printf("  %d",d[i][j]);
   if(d[i][j+1]==d[i][j+2])
    break;
  }
  printf("\n");
 }
 }            
 
int main()
{
 int a;
 init();
    find();
    print();
    a=getchar();
while(a!=EOF)
    a=getchar();
 return 1;
}