Dijkstra最短路徑

請依照測資起點為0 請找出0對其他點的最短路徑
並且秀出其路徑
a.in

6 7
0 1 2
2 4 3
0 2 1
1 3 4
4 5 2
2 1 1
4 3 2

複製代碼

1.先畫圖
2.秀出成本
3.秀出路徑

新手上路

Rank: 1

5^#

Alen發表於 2011-9-3 21:33 | 只看該作者

今日進度:

Program :

#include<iostream>
#include<fstream>
using namespace std ;
const int M = 9999 ;
int main()
{
ifstream fin("pa.in") ;
int a , b ;
fin >> a >> b ;
int v = a;
int visit[a] ;
int d[a] ;
cout << "以0為起點: " << endl;
cout << endl;
cout << "各點之關係圖 : " << endl;
cout << endl;
int map[a][a] ;
//init
for( int i = 0 ; i < a ; i ++ )
{
for( int j = 0 ; j < a ; j ++ )
{
map[i][j] = M ;
}
visit[i] = false ;
d[i] = M ;
}
for( int i = 0 ; i < b ; i ++ )
{
int c , d , cost;
fin >> c >> d >> cost;
map[c][d] = cost ;
map[d][c] = cost ;
}
// draw map
int loc[4] = {0} ;
for( int i = 0 ; i < a ; i ++ )
{
int min = 999 ;
loc[0] = 0 ;
for( int j = 0 ; j < a ; j ++ )
{
if ( map[i][j] < min )
{
min = map[i][j] ;
loc[j] = j ;
}
cout << map[i][j] << "\t" ;
}
cout << endl ;
}
cout << endl;
cout << "成本關係圖 : " << endl;
cout << endl;
int mapcost[a][a] ;
int parent[a] ;
const int M = 9999 ; // far
// init map and draw map
for( int i = 0 ; i < v ; i ++ )
{
for( int j = 0 ; j < v ; j ++ )
{
mapcost[i][j] = M ;
}
visit[i] = false ;
d[i] = M ;
}
// dijkstra
d[0] = 0 ;
int path[a] ;
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 ;
path[index] = i;
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 k = 0 ; k < v ; k ++ )
{
cout << d[k] << "\t" ;
}
cout << endl ;
}
}
}
for( int i = 0 ; i < v ; i ++ )
{
cout << d[i] << "\t" ;
}
cout << endl ;
cout << endl;
cout << "最短路徑 1 : " << endl;
cout << endl;
cout << path[0] ;
for (int i = 1; i < a;i++)
{
for (int j = 0; j < a;j++)
{
if (path[i] == j)
{
cout << " -> " << path[i] ;
}
}
}cout << endl;
cout << endl;
cout << "所有路徑成本圖 : " << endl;
cout << endl;
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 ;
}
cout << endl;
cout << "----------------------我是分隔線----------------------" << endl;
cout << endl;
cout << "以3為起點: " << endl;
cout << endl;
system("Pause") ;
}

複製代碼

Result :

以0為起點:
各點之關係圖 :
9999 2 1 9999 9999 9999
2 9999 1 4 9999 9999
1 1 9999 9999 3 9999
9999 4 9999 9999 2 9999
9999 9999 3 2 9999 2
9999 9999 9999 9999 2 9999
成本關係圖 :
0 2 9999 9999 9999 9999
0 2 1 9999 9999 9999
0 2 1 9999 4 9999
0 2 1 6 4 9999
0 2 1 6 4 6
0 2 1 6 4 6
最短路徑 1 :
0 -> 2 -> 1 -> 4 -> 3 -> 5
所有路徑成本圖 :
1 -> 0 -> cost 2
2 -> 0 -> cost 1
3 -> 1 -> 0 -> cost 6
4 -> 2 -> 0 -> cost 4
5 -> 4 -> 2 -> 0 -> cost 6
----------------------我是分隔線----------------------
以3為起點:
請按任意鍵繼續 . . .

複製代碼

我是來去無蹤的..

..士豪(Alen)黑輪

TOP

新手上路

Rank: 1

4^#

蔡昀修發表於 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") ;
}

TOP