Dijkstra算法的实现

    //Dijkstra.h
    #define max 6
    int find_minimum_route(int route[100],int visit[100],int *position,int vertex_number)
    {
     int i;
     int tag=0;
     int temp;
     i=0;
     temp=9999;
     while(i     {
      if((temp>route[i])&&visit[i]==0)
      {
       temp=route[i];
       *position=i;
       tag=1;
      }
      i++;
     }
     if(tag=1)return temp;
     else
     {
      *position=vertex_number;
      return 9999;
     }
    }
    void Dijkstra(int Graph_list_search[max][max],int first,int end){
     int i;
     int Graph_minimum_Distance[max];
     int Graph_visit[max];
     int Graph_minimum_road[max][max];
     for(i=0;i     {
      Graph_minimum_Distance[i]=Graph_list_search[first][i];
      Graph_visit[i]=0;
      for(int w=0;w       Graph_minimum_road[i][w]=0;//store the road
      if(Graph_minimum_Distance[i]<9999){
       Graph_minimum_road[i][first]=1;
       Graph_minimum_road[i][i]=1;
      }
     }
     int position;
     int minimum_Distance;
     Graph_minimum_Distance[first]=0;
     Graph_visit[first]=1;
     for(int h=1;h      minimum_Distance=find_minimum_route(Graph_minimum_Distance,Graph_visit,&position,max);
      Graph_visit[position]=1;
      for(i=0;i       if(Graph_visit[i]==0){
        if(Graph_minimum_Distance[i]>minimum_Distance+Graph_list_search[position][i]){
         Graph_minimum_Distance[i]=minimum_Distance+Graph_list_search[position][i];
         for(int j=0;j          Graph_minimum_road[i][j]=Graph_minimum_road[position][j];
         Graph_minimum_road[i][i]=1;
        }
       }
      }//while(i     }
     printf("The minimum road is(vertex%d->vertex%d):\n",first,end);
     for(i=0;i");i++){
      if(Graph_minimum_road[end][i]==1)printf("vertex%d",i);
     }
     printf("\n");
    }
   //main.h
    #include
    #include "Dijkstra.h"
    int main()
    {
     int  Graph_list_search[max][max]={{0,3,2,5,9999,9999},
     {9999,0,9999,2,9999,9999},
     {9999,9999,0,1,9999,9999},
     {9999,9999,9999,0,9999,5},
     {9999,9999,5,3,0,1},
     {9999,9999,9999,9999,9999,0}};
     printf_edge(Graph_list_search);
     Dijkstra(Graph_list_search,0,5);
     return 0;
    }

    //Dijkstra.h
    #define max 6
    int find_minimum_route(int route[100],int visit[100],int *position,int vertex_number)
    {
     int i;
     int tag=0;
     int temp;
     i=0;
     temp=9999;
     while(i     {
      if((temp>route[i])&&visit[i]==0)
      {
       temp=route[i];
       *position=i;
       tag=1;
      }
      i++;
     }
     if(tag=1)return temp;
     else
     {
      *position=vertex_number;
      return 9999;
     }
    }
    void Dijkstra(int Graph_list_search[max][max],int first,int end){
     int i;
     int Graph_minimum_Distance[max];
     int Graph_visit[max];
     int Graph_minimum_road[max][max];
     for(i=0;i     {
      Graph_minimum_Distance[i]=Graph_list_search[first][i];
      Graph_visit[i]=0;
      for(int w=0;w       Graph_minimum_road[i][w]=0;//store the road
      if(Graph_minimum_Distance[i]<9999){
       Graph_minimum_road[i][first]=1;
       Graph_minimum_road[i][i]=1;
      }
     }
     int position;
     int minimum_Distance;
     Graph_minimum_Distance[first]=0;
     Graph_visit[first]=1;
     for(int h=1;h      minimum_Distance=find_minimum_route(Graph_minimum_Distance,Graph_visit,&position,max);
      Graph_visit[position]=1;
      for(i=0;i       if(Graph_visit[i]==0){
        if(Graph_minimum_Distance[i]>minimum_Distance+Graph_list_search[position][i]){
         Graph_minimum_Distance[i]=minimum_Distance+Graph_list_search[position][i];
         for(int j=0;j          Graph_minimum_road[i][j]=Graph_minimum_road[position][j];
         Graph_minimum_road[i][i]=1;
        }
       }
      }//while(i     }
     printf("The minimum road is(vertex%d->vertex%d):\n",first,end);
     for(i=0;i");i++){
      if(Graph_minimum_road[end][i]==1)printf("vertex%d",i);
     }
     printf("\n");
    }
    void printf_edge(int Graph_list_search[max][max])
    {
     printf("The example edge is:\n");
     for(int i=0;i      for(int j=0;j       printf("%d ",Graph_list_search[i][j]);
      printf("\n");
     }
    }

  void printf_edge(int Graph_list_search[max][max])
    {
     printf("The example edge is:\n");
     for(int i=0;i      for(int j=0;j       printf("%d ",Graph_list_search[i][j]);
      printf("\n");
     }
    }