最短路 spfa， dijkstra， Floyd

spfa

 1 #include <stdio.h>
 2 #include <queue>
 3 using namespace std;
 4 
 5 #define RANGE 101
 6 #define MAX 0x3f3f3f3f
 7 int cost[RANGE][RANGE];
 8 int d[RANGE];
 9 bool used[RANGE];
10 int n,m;
11 
12 void spfa( int s )
13 {
14   int i,now;
15   // 初始化
16   for( i=1;i<=n;++i )
17   {
18     d[i]=MAX;
19     used[i]=false;
20   }
21 
22   d[s]=0;
23   queue <int> q;
24   q.push(s);
25   used[s] = true;
26 
27   while(!q.empty())
28   {
29     now = q.front();
30     q.pop();
31     used[now] = false;
32     for(i = 1; i <= n; i++)
33     {
34       if(d[i] > d[now] + cost[now][i])
35       {
36         d[i] = d[now] + cost[now][i];
37         if(used[i] == 0)
38         {
39           q.push(i);
40           used[i] = true;
41         }
42       }
43     }
44   }
45 }
46 
47 int main()
48 {
49   int i,j,A,B,C;
50   while( scanf("%d%d",&n,&m) )
51   {
52     if( !n && !m )  break;
53     // 初始化
54     for( i=1;i<=n;++i )
55       for( j=1;j<=i;++j )
56         if( i==j )  cost[i][j]=0;
57         else    cost[i][j]=cost[j][i]=MAX;
58 
59     for( i=0;i<m;++i )
60     {
61       scanf("%d%d%d",&A,&B,&C);
62       cost[A][B]=cost[B][A]=C;
63     }
64 
65     spfa(1);
66     printf("%d
",d[n]);
67   }
68   return 0;
69 }

View Code

dijkstra

 1 #include <stdio.h>
 2 #define MAX 0x3f3f3f3f
 3 #define RANGE 101
 4 
 5 int cost[RANGE][RANGE];
 6 int d[RANGE];
 7 bool used[RANGE];
 8 
 9 int n,m;
10 int Min( int a,int b )
11 {
12   return a<b?a:b;
13 }
14 
15 void Dijkstra( int s )
16 {
17   int i,v,u;
18   for( i=1;i<=n;++i )
19   {
20     used[i]=false;
21     d[i]=cost[1][i];
22   }
23   d[s]=0;
24 
25   while( true )
26   {
27     v=-1;
28     for( u=1;u<=n;++u )
29       if( !used[u] && ( v==-1 || d[u]<d[v]) )
30         v=u;
31     if( v==-1 ) break;
32     used[v]=true;
33 
34     for( u=1;u<=n;++u )
35       d[u]=Min( d[u],d[v]+cost[v][u] );
36   }
37 }
38 
39 int main()
40 {
41   int A,B,C,i,j;
42 
43   while( scanf("%d%d",&n,&m) )
44   {
45     if( !n && !m )  break;
46 
47     // 初始化
48     for( i=1;i<=n;++i )
49       for( j=1;j<=i;++j )
50         if( i==j )  cost[i][j]=0;
51         else    cost[i][j]=cost[j][i]=MAX;
52 
53     for( i=0;i<m;++i )
54     {
55       scanf("%d%d%d",&A,&B,&C);
56       cost[A][B]=cost[B][A]=C;
57     }
58 
59     Dijkstra(1);
60     printf("%d
",d[n]);
61   }
62   return 0;
63 }

View Code

floyd

 1 #include <stdio.h>
 2 #define MAX 0x3f3f3f3f
 3 #define RANGE 105
 4 
 5 int d[RANGE][RANGE];
 6 int n;
 7 
 8 int Min( int a,int b )
 9 {
10   return a<b?a:b;
11 }
12 void warshall_floyd( void )
13 {
14   int i,j,k;
15   for( k=1;k<=n;++k )
16     for( i=1;i<=n;++i )
17       for( j=1;j<=n;++j )
18         d[i][j]=Min( d[i][j],d[i][k]+d[k][j] );
19 }
20 
21 int main()
22 {
23   int m,A,B,C,i,j;
24 
25   while( scanf("%d%d",&n,&m) )
26   {
27     if( !n && !m )  break;
28 
29     // 初始化
30     for( i=1;i<=n;++i )
31       for( j=1;j<=i;++j )
32       {
33         if( i==j ) d[i][j]=0;
34         else    d[i][j]=d[j][i]=MAX;
35       }
36 
37     // 输入
38     for( i=0;i<m;++i )
39     {
40       scanf("%d%d%d",&A,&B,&C);
41       d[A][B]=d[B][A]=C;
42     }
43 
44     // floyd算法求最短路
45     warshall_floyd();
46     printf("%d
",d[1][n]);
47   }
48   return 0;
49 }

View Code