dijkstra算法

2008-10-02


#include<iostream>
using namespace std;
#define MAX 10000
int edge[16][16];
int dijkstra(int start,int end,int path[]);
void Output(int path[],int end);
int main(void){
    for(int i=0;i<16;i++){
        for(int j=1;j<16;j++)
            edge[i][j] = MAX;
        edge[i][i]=0;
    }
    edge[0][1] = 2;
    edge[0][2] = 3;
    edge[1][3] = 1;
    edge[1][4] = 2;
    edge[2][4] = 5;
    edge[2][5] = 4;
    edge[3][6] = 3;
    edge[3][7] = 2;
    edge[4][7] = 4;
    edge[4][8] = 2;
    edge[5][8] = 4;
    edge[5][9] = 4;
    edge[6][10] = 1;
    edge[7][10] = 3;
    edge[7][11] = 1;
    edge[8][11] = 1;
    edge[8][12] = 3;
    edge[9][12] = 3;
    edge[10][13] = 4;
    edge[11][13] = 2;
    edge[11][14] = 2;
    edge[12][14] = 2;
    edge[14][15] = 3;
    edge[13][15] = 2;
   
    int start,end;
    int path[20];
    cin>>start>>end;
   
    int len = dijkstra(start,end,path);
    if(len<MAX){
    cout<<len<<endl;
    Output(path,end);
    }
    else{
    cout<<"No path";
    }
       
    getchar();getchar();
   
    return 0;
}
int find_min(int num[],int n,bool state[]){
    int r=0;
    while(state[r]) r++;
    for(int i=1;i<n;i++)
        if(num[r]>num[i]&&!state[i]) r = i;
       
    return r;
}//在s2中选择最短的点

int dijkstra(int start,int end,int path[]){
     bool state[16] = {0,0,0,0,0,0};
     state[start] = true;
     int mindis[16],newl;
    
     for(int i=0;i<16;i++){
         mindis[i] = edge[start][i];
         if(edge[start][i]<MAX)
            path[i] = start;
         else
            path[i] = -1;
     }
        
     while(!state[end]){
          int min = find_min(mindis,16,state);
          if(mindis[min]>=MAX) break;
          state[min] = true;
         
          for(int i=0;i<16;i++){
              if(!state[i]&&edge[min][i]<MAX){
              newl = mindis[min]+edge[min][i];
              if(newl<mindis[i]){
                 mindis[i] = newl;
                 path[i] = min;
                 }
              }
          }
     }
    
     return mindis[end];
}
void Output(int path[],int end){
     if(path[end]==-1) cout<<"No path";
     else if(path[end] == end) cout<<end<<" ";
     else{ Output(path,path[end]); cout<<end<<" ";}
}