Advertisement
jhon345

Untitled

Sep 4th, 2016
1,174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # include <stdio.h>
  2. # define MAX_NODE 8
  3. # define INFINITY 1000000
  4.  
  5.  int n, dist[MAX_NODE][MAX_NODE];
  6.  
  7. void Print_Matrix (int);
  8.  
  9.  
  10.  
  11.  struct state{
  12.         int predecessor;
  13.         int lenght;
  14.         int label;
  15.     }state [MAX_NODE];
  16.    
  17.  
  18.  int main(){
  19.  
  20.    
  21.    
  22.    
  23.     int  nodes ;
  24.     int cont = 1;
  25.    
  26.     printf("enter the amount of nodes of matrix : \n");
  27.     scanf("%d", &nodes);
  28.     //printf("%d", nodes);
  29.    
  30.     printf("To assemble  distance matrix enter a value :[distance]\n");
  31.    
  32.     for(int line = 0; line < nodes; line++)
  33.     {
  34.         for(int column = 0; column < nodes ; column++)
  35.         {
  36.             printf("Establish a conect between %d --> %d [nodes] ? 0 to N : ",line,column);
  37.            
  38.               scanf("%d", &dist[line][column]);
  39.         }
  40.     }
  41.    
  42.    
  43.  
  44.     int  paht[MAX_NODE];
  45.  
  46.     int s,t;
  47.     printf("Enter the origin and destination :");
  48.     scanf("%d %d",&t ,&s);
  49.    
  50.     int i, k, min;
  51.     struct state *p;
  52.    
  53.     for (p = &state[0]; p < &state[nodes]; p++){
  54.    
  55.         p->predecessor =-1;
  56.         p-> lenght = INFINITY;
  57.         p-> label = -1;
  58.     }
  59.    
  60.     state[t].lenght = 0;
  61.     state[t].label = 1;
  62.     k = t;
  63.     do{
  64.    
  65.         for (i = 0; i < nodes ;i++){
  66.             if(dist[k][i] != 0 && state[i].label == -1){
  67.                 if(state[k].lenght + dist[k][i] < state[i].lenght){
  68.                     state[i].predecessor = k;
  69.                     state[i].lenght = state[k].lenght + dist[k][i];
  70.                 }
  71.             }
  72.         }
  73.        
  74.         k = 0;
  75.         min = INFINITY;
  76.        
  77.        
  78.         for(i = 0 ;i <  nodes ; i++){
  79.             if(state[i].label == -1 && state[i].lenght < min  ){
  80.                 min = state[i].lenght;
  81.                 k = i;
  82.                 cont++;
  83.             }
  84.         }
  85.        
  86.         state[k].label = 1;
  87.  
  88.     }while(k != s);
  89.    
  90.     i = 0 , k = s;
  91.    
  92.     do{
  93.         paht[i++] = k ;
  94.         k = state[k].predecessor;//printf("%d", state[k].predecessor);
  95.        
  96.      }while(k >= 0);
  97.      
  98.      
  99.     printf("Melhor Caminho :|Best paht : \n");
  100.    
  101.     int value = 0,h,g;
  102.    
  103.     for(i = 0;i <= s; i++){
  104.        
  105.         if(paht[i]!= t){
  106.             printf("%d--> ",paht[i]);
  107.            
  108.         }else{
  109.             break;
  110.         }          
  111.     }
  112.    
  113.     printf("%d-->",t);
  114.     printf("Start\n");
  115.    
  116.     for(i = 0;i <= s; i++){
  117.         h = paht[i]; g = paht[i+1];
  118.         if(paht[i]!= t){
  119.             value += dist[g][h];
  120.         }else{
  121.             break;
  122.         }  
  123.                    
  124.     }
  125.     printf("Route Cost :%d\n",value);
  126.     printf("jumps :%d",cont);
  127.     /*
  128.     printf("Distancias Percorridas|Distance traveled : \n");
  129.     printf("Start");
  130.    
  131.         for (i = 0; i<=s ; i++  ){ 
  132.             printf(" --> %d",state[i].lenght  );
  133.     }
  134.     printf("\n");
  135.     */
  136.    
  137.    
  138.     Print_Matrix(nodes);
  139.  
  140.    
  141.     return 0;
  142.  }
  143.  
  144.  void Print_Matrix(int n){
  145.     printf("             Distance Matrix\n");
  146.     printf("---------------------------------------------\n");
  147.     int k = 1;
  148.    
  149.     printf("\t\t|  x|");
  150.     for(int i = 0; i<= n ;i++){
  151.         for(int j = 0; j<n; j++){
  152.             if(i == 0){
  153.                 printf("|%3d|", j);
  154.             }else{
  155.                 if(k == 1){
  156.                     printf("\t\t|%3d|", i-1);
  157.                     k--;
  158.                 }
  159.                 printf("|%3d|",dist[i-1][j] );
  160.                
  161.             }
  162.         }  
  163.         printf("\n");
  164.  
  165.         k= 1;
  166.        
  167.     }
  168.     printf("\n");
  169.    
  170. }
Advertisement
RAW Paste Data Copied
Advertisement