sdut2143图结构练习—

sdut2143图结构练习——最短路径

从书上大体看了看思想然后照着模板打由于没考虑重边的问题WA一次

Dijkstra算法

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int w[101][101];
 4 #define INF 0x3f3f3f3f
 5 int main()
 6 {

 7     int i, j, k,n,m,d[5000],f[101],x,y,e;
 8     while(scanf("%d%d", &n, &m)!=EOF)
 9     {
10         memset(f, 0, sizeof(f));
11         memset(w,INF,sizeof(w));
12         d[1] = 0;
13         for(i = 2 ; i <= n ; i++)
14             d[i] = INF;
15         for(i = 1 ; i <= m ; i++)
16         {
17             scanf("%d%d%d", &x,&y,&e);
18             if(w[x][y]>e)
19             {
20                 w[x][y] = e;
21                 w[y][x] = e;
22             }
23         }
24         for(i = 1 ; i <= n ; i++)
25         {
26             int min = INF;
27             for(j = 1 ; j <= n ; j++)
28                 if(!f[j]&&min>=d[j])
29                     min = d[k=j];
30             f[k] = 1;
31             for(j = 1 ; j <= n ; j++)
32                 if(d[j]>d[k]+w[k][j])
33                 d[j]=d[k]+w[k][j];
34         }    
35         printf("%d\n",d[n]);
36     }
37     return 0;
38 }

Floyd算法

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF 0x3f3f3f3f
 4 int main()
 5 {
 6     int i, j, k, n, m, d[101][101],x,y,e;
 7     while(scanf("%d%d", &n,&m)!=EOF)
 8     {
 9         memset(d,INF,sizeof(d));
10         for(i = 1 ;i <= n ;i++)
11             d[i][i] = 0;
12         for(i = 1 ; i <= m ; i++)
13         {
14             scanf("%d%d%d", &x,&y,&e);
15             if(d[x][y]>e)
16             {
17                 d[x][y] = e;
18                 d[y][x] = e;
19             }
20         }
21         for(k =1 ;k<=n ;k++)
22             for(i = 1 ;i <= n ; i++)
23                 for(j = 1 ;j <= n ; j++)
24                     if(d[i][j]>d[i][k]+d[k][j])
25                         d[i][j] = d[i][k]+d[k][j];
26         printf("%d\n",d[1][n]);
27     }
28     return 0;
29 }