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>

  3. using namespace std ;

  4. const int M = 9999 ;

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

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

  8. 成本關係圖 :

  9. 0       2       9999    9999    9999    9999
  10. 0       2       1       9999    9999    9999
  11. 0       2       1       9999    4       9999
  12. 0       2       1       6       4       9999
  13. 0       2       1       6       4       6
  14. 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>

  3. using namespace std ;

  4. const int M = 9999 ;

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

  2. 各點之關係圖 :

  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

  9. 成本關係圖 :

  10. 0       2       9999    9999    9999    9999
  11. 0       2       1       9999    9999    9999
  12. 0       2       1       9999    4       9999
  13. 0       2       1       6       4       9999
  14. 0       2       1       6       4       6
  15. 0       2       1       6       4       6

  16. 最短路徑 1 :

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

  18. 所有路徑成本圖 :

  19. 1  ->  0  ->  cost 2
  20. 2  ->  0  ->  cost 1
  21. 3  ->  1  ->  0  ->  cost 6
  22. 4  ->  2  ->  0  ->  cost 4
  23. 5  ->  4  ->  2  ->  0  ->  cost 6

  24. ----------------------我是分隔線----------------------

  25. 以3為起點:

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





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