Board logo

標題: Dijkstra最短路徑 [打印本頁]
作者: justtim    時間: 2011-8-27 21:50     標題: Dijkstra最短路徑

請依照測資 起點為0 請找出0對其他點的最短路徑
並且秀出其路徑
a.in
  1. 6 7
  2. 0 1 2
  3. 2 4 3
  4. 0 2 1
  5. 1 3 4
  6. 4 5 2
  7. 2 1 1
  8. 4 3 2
複製代碼
1.先畫圖
2.秀出成本
3.秀出路徑

作者: Alen    時間: 2011-8-27 21:54

本帖最後由 Alen 於 2011-8-27 21:57 編輯

回復 1# justtim

使用p.in

Program :
  1. #include<iostream>
  2. #include<fstream>

  4. using namespace std ;

  6. const int M = 9999 ;

  8. int main()
  9. {
  10.     ifstream fin("pa.in") ;
  11.     int a , b ;
  12.     fin >> a >> b ;
  13.     int v = a;
  14.     int visit[a] ;
  15.     int d[a] ;
  16.    
  17.     cout << "各點之關係圖 : " << endl;
  18.     cout << endl;
  19.     int map[a][a] ;
  20.     //init
  21.     for( int i = 0 ; i < a ; i ++ )
  22.     {
  23.         for( int j = 0 ; j < a ; j ++ )     
  24.         {
  25.             map[i][j] = M ;     
  26.         }
  27.         visit[i] = false ;
  28.         d[i] = M ;
  29.     }   
  30.     for( int i = 0 ; i < b ; i ++ )
  31.     {
  32.          int c , d , cost;
  33.          fin >> c >> d >> cost;
  34.          map[c][d] = cost ;
  35.          map[d][c] = cost ;
  36.     }
  37.     // draw map
  38.     int loc[4] = {0} ;
  39.     for( int i = 0 ; i < a ; i ++ )
  40.     {
  41.         int min = 999 ;
  42.         
  43.         loc[0] = 0 ;
  44.         for( int j = 0 ; j < a ; j ++ )     
  45.         {
  46.             if ( map[i][j] < min )
  47.             {
  48.                min = map[i][j] ;
  49.                loc[j] = j ;     
  50.             }
  51.             cout << map[i][j] << "\t" ;     
  52.         }
  53.         cout << endl ;
  54.     }
  55.     cout << endl;
  56.    
  57.    
  58.     cout << "成本關係圖 : " << endl;
  59.     cout << endl;
  60.    
  61.     int mapcost[a][a] ;
  62.     int parent[a] ;
  63.     const int M = 9999 ; // far   
  64.    
  65.     // init map and draw map
  66.     for( int i = 0 ; i < v ; i ++ )
  67.     {
  68.         for( int j = 0 ; j < v ; j ++ )     
  69.         {
  70.             mapcost[i][j] = M ;     
  71.         }
  72.         visit[i] = false ;
  73.         d[i] = M ;
  74.     }
  75.    
  76.         // dijkstra
  77.     d[0] = 0 ;
  78.     parent[0] = 0 ;
  79.     for( int i = 0 ; i < v ; i ++ )
  80.     {
  81.          int min = M ;
  82.          int index = -1 ;
  83.          for( int j = 0 ; j < v ; j ++ )
  84.          {
  85.              if( !visit[j] && d[j] < min )
  86.              {
  87.                  min = d[j] ;
  88.                  index = j ;
  89.              }     
  90.          }
  91.          
  92.          if( index == -1 ) break ;
  93.          visit[index] = true ;
  94.          for( int j = 0 ; j < v ; j ++ )
  95.          {
  96.              if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
  97.              {
  98.                  d[j] = d[index] + map[index][j] ;
  99.                  parent[j] = index ;  
  100.    
  101.     for( int k = 0 ; k < v ; k ++ )
  102.     {
  103.         cout << d[k] << "\t" ;
  104.     }
  105.     cout << endl ;                  
  106.    
  107.              }
  108.          }   
  109.     }
  110.    
  111.     for( int i = 0 ; i < v ; i ++ )
  112.     {
  113.         cout << d[i] << "\t" ;
  114.     }
  115.     cout << endl ;
  116.    
  117.     system("Pause") ;
  118. }
複製代碼
Result :
  1. 各點之關係圖 :

  3. 9999    2       1       9999    9999    9999
  4. 2       9999    1       4       9999    9999
  5. 1       1       9999    9999    3       9999
  6. 9999    4       9999    9999    2       9999
  7. 9999    9999    3       2       9999    2
  8. 9999    9999    9999    9999    2       9999

  10. 成本關係圖 :

  12. 0       2       9999    9999    9999    9999
  13. 0       2       1       9999    9999    9999
  14. 0       2       1       9999    4       9999
  15. 0       2       1       6       4       9999
  16. 0       2       1       6       4       6
  17. 0       2       1       6       4       6
複製代碼
作者: Alen    時間: 2011-8-27 21:57

有Po了!!
作者: 蔡昀修    時間: 2011-9-3 20:53

#include<iostream>
#include<fstream>

using namespace std ;

int main()
{
    ifstream fin("pa.in") ;
   
    int v,w ;
    fin >> v >> w ;
    int map[v][v] ;
    int parent[v] ;
    int visit[v] ;
    int d[v] ;
    const int M = 9999 ; // far   
   
    // init map and draw map
    for( int i = 0 ; i < v ; i ++ )
    {
        for( int j = 0 ; j < v ; j ++ )     
        {
            map[i][j] = M ;     
        }
        visit[i] = false ;
        d[i] = M ;
    }
   
    for( int i = 0 ; i < w ; i ++ )
    {
        int a,b,c ;
        fin >> a >> b >> c ;
        map[a][b] = c ;
        map[b][a] = c ;   
    }

/*    for( int i = 0 ; i < v ; i ++ )
    {
        for( int j = 0 ; j < v ; j ++ )     
        {
            cout << map[i][j] << "\t" ;     
        }
        cout << endl ;
    }*/
                     
    // dijkstra
    d[0] = 0 ;
    parent[0] = 0 ;
    for( int i = 0 ; i < v ; i ++ )
    {
         int min = M ;
         int index = -1 ;
         for( int j = 0 ; j < v ; j ++ )
         {
             if( !visit[j] && d[j] < min )
             {
                 min = d[j] ;
                 index = j ;
             }     
         }
         
         if( index == -1 ) break ;
         visit[index] = true ;
         for( int j = 0 ; j < v ; j ++ )
         {
             if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
             {
                 d[j] = d[index] + map[index][j] ;
                 parent[j] = index ;                    
   
             }
         }   
    }
   
    for( int i = 1 ; i < v ; i ++ )
    {
        cout << i << "->" ;         
        int pre = i ;
        while( parent[pre] != pre )
        {
           pre = parent[pre] ;
           cout << pre << "->" ;
        }
        cout << "cost" << d[i] << endl ;
    }
   
   
    system("Pause") ;
}
作者: Alen    時間: 2011-9-3 21:33

今日進度:



Program :
  1. #include<iostream>
  2. #include<fstream>

  4. using namespace std ;

  6. const int M = 9999 ;

  8. int main()
  9. {
  10.     ifstream fin("pa.in") ;
  11.     int a , b ;
  12.     fin >> a >> b ;
  13.     int v = a;
  14.     int visit[a] ;
  15.     int d[a] ;
  16.    
  17.     cout << "以0為起點: " << endl;
  18.     cout << endl;
  19.    
  20.    
  21.     cout << "各點之關係圖 : " << endl;
  22.     cout << endl;
  23.     int map[a][a] ;
  24.     //init
  25.     for( int i = 0 ; i < a ; i ++ )
  26.     {
  27.         for( int j = 0 ; j < a ; j ++ )     
  28.         {
  29.             map[i][j] = M ;     
  30.         }
  31.         visit[i] = false ;
  32.         d[i] = M ;
  33.     }   
  34.     for( int i = 0 ; i < b ; i ++ )
  35.     {
  36.          int c , d , cost;
  37.          fin >> c >> d >> cost;
  38.          map[c][d] = cost ;
  39.          map[d][c] = cost ;
  40.     }
  41.     // draw map
  42.     int loc[4] = {0} ;
  43.     for( int i = 0 ; i < a ; i ++ )
  44.     {
  45.         int min = 999 ;
  46.         
  47.         loc[0] = 0 ;
  48.         for( int j = 0 ; j < a ; j ++ )     
  49.         {
  50.             if ( map[i][j] < min )
  51.             {
  52.                min = map[i][j] ;
  53.                loc[j] = j ;     
  54.             }
  55.             cout << map[i][j] << "\t" ;     
  56.         }
  57.         cout << endl ;
  58.     }
  59.     cout << endl;
  60.    
  61.    
  62.     cout << "成本關係圖 : " << endl;
  63.     cout << endl;
  64.    
  65.     int mapcost[a][a] ;
  66.     int parent[a] ;
  67.     const int M = 9999 ; // far   
  68.    
  69.     // init map and draw map
  70.     for( int i = 0 ; i < v ; i ++ )
  71.     {
  72.         for( int j = 0 ; j < v ; j ++ )     
  73.         {
  74.             mapcost[i][j] = M ;     
  75.         }
  76.         visit[i] = false ;
  77.         d[i] = M ;
  78.     }
  79.    
  80.         // dijkstra
  81.     d[0] = 0 ;
  82.     int path[a] ;
  83.     parent[0] = 0 ;
  84.     for( int i = 0 ; i < v ; i ++ )
  85.     {
  86.          int min = M ;
  87.          int index = -1 ;
  88.          for( int j = 0 ; j < v ; j ++ )
  89.          {
  90.              if( !visit[j] && d[j] < min )
  91.              {
  92.                  min = d[j] ;
  93.                  index = j ;
  94.              }     
  95.          }
  96.          
  97.          if( index == -1 ) break ;
  98.          visit[index] = true ;
  99.          path[index] = i;
  100.          for( int j = 0 ; j < v ; j ++ )
  101.          {
  102.              if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
  103.              {
  104.                  d[j] = d[index] + map[index][j] ;
  105.                  parent[j] = index ;  
  106.    
  107.     for( int k = 0 ; k < v ; k ++ )
  108.     {
  109.         cout << d[k] << "\t" ;
  110.     }
  111.     cout << endl ;                  
  112.    
  113.              }
  114.          }   
  115.     }
  116.    
  117.    
  118.     for( int i = 0 ; i < v ; i ++ )
  119.     {
  120.         cout << d[i] << "\t" ;
  121.     }
  122.     cout << endl ;
  123.    
  124.     cout << endl;
  125.     cout << "最短路徑 1 : " << endl;
  126.     cout << endl;
  127.    
  128.     cout << path[0] ;
  129.    
  130.     for (int i = 1; i < a;i++)
  131.     {
  132.        for (int j = 0; j < a;j++)
  133.        {
  134.         
  135.         if (path[i] == j)
  136.         {
  137.            cout << "  ->  " << path[i] ;            
  138.         }
  139.             
  140.     }
  141.         
  142.             
  143.     }cout << endl;
  144.     cout << endl;
  145.    
  146.     cout << "所有路徑成本圖 : " << endl;
  147.     cout << endl;
  148.    
  149.     for( int i = 1 ; i < v ; i ++ )
  150.     {
  151.         cout << i << "  ->  " ;         
  152.         int pre = i ;
  153.         while( parent[pre] != pre )
  154.         {
  155.            pre = parent[pre] ;
  156.            cout << pre << "  ->  " ;
  157.         }
  158.         cout << "cost " << d[i] << endl ;
  159.     }
  160.    
  161.     cout << endl;
  162.    
  163.    
  164.     cout << "----------------------我是分隔線----------------------" << endl;
  165.     cout << endl;
  166.     cout << "以3為起點: " << endl;
  167.     cout << endl;
  168.    
  169.      
  170.    
  171.    
  172.    
  173.    
  174.     system("Pause") ;
  175. }
複製代碼
Result :
  1. 以0為起點:

  3. 各點之關係圖 :

  5. 9999    2       1       9999    9999    9999
  6. 2       9999    1       4       9999    9999
  7. 1       1       9999    9999    3       9999
  8. 9999    4       9999    9999    2       9999
  9. 9999    9999    3       2       9999    2
  10. 9999    9999    9999    9999    2       9999

  12. 成本關係圖 :

  14. 0       2       9999    9999    9999    9999
  15. 0       2       1       9999    9999    9999
  16. 0       2       1       9999    4       9999
  17. 0       2       1       6       4       9999
  18. 0       2       1       6       4       6
  19. 0       2       1       6       4       6

  21. 最短路徑 1 :

  23. 0  ->  2  ->  1  ->  4  ->  3  ->  5

  25. 所有路徑成本圖 :

  27. 1  ->  0  ->  cost 2
  28. 2  ->  0  ->  cost 1
  29. 3  ->  1  ->  0  ->  cost 6
  30. 4  ->  2  ->  0  ->  cost 4
  31. 5  ->  4  ->  2  ->  0  ->  cost 6

  33. ----------------------我是分隔線----------------------

  35. 以3為起點:

  37. 請按任意鍵繼續 . . .
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2