M.J的blog

algorithm,ACM-ICPC
随笔 - 39, 文章 - 11, 评论 - 20, 引用 - 0
数据加载中……

【图论】最短路和最小生成树

两个算法具有相当大的相似性,而且都用到了贪心思想,所以把他们放到一起。最短路常用的算法有dijkstra,bellman-ford,floyd。而最小生成树则是prim和kruskal。下面是各个算法的模板。
Dijkstra:
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF 0x1f1f1f1f
 4 #define M 1001
 5 int map[M][M],dis[M];
 6 bool flag[M];
 7 void dijkstra(int s,int n,int t)            //s是源点,n是点的个数,t是目的点
 8 {
 9     int i,j,k,md,temp;
10     for(i=1;i<=n;i++)
11         dis[i]=INF;                        //初始化将所有dis置为无穷大,源点为0
12     dis[s]=0;
13     memset(flag,false,sizeof(flag));       //开始flag全部为false,表示集合为空
14     for(i=1;i<n;i++){                      //进行n-1次迭代,每次找出不在集合中的最小边
15         md=INF;                                           
16         for(j=1;j<=n;j++){
17             if(!flag[j]&&dis[j]<md){
18                 md=dis[j];
19                 temp=j;
20             }
21         } 
22         if(temp==t) break;                 //如果遇到目的点,可以跳出了
23         flag[temp]=true;                   //将这个最小边的点加入集合
24         for(j=1;j<=n;j++){
25             if(!flag[j]&&md+map[temp][j]<dis[j])    //对所有出边进行松弛操作
26                 dis[j]=md+map[temp][j];
27         }
28     }
29 }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
相应的最小生成树的prim模板:

 1 #include<iostream>
 2 #define INF 0x1f1f1f1f
 3 #define M 1000
 4 using namespace std;
 5 double dis[M],map[M][M];
 6 bool flag[M];
 7 int prim(int s,int n)                        //s为起点,n为点的个数
 8 {
 9     int i,j,k,temp,md,total=0;
10     for(i=1;i<=n;i++)
11         dis[i]=map[s][i];                    //与最短路不同,而是将dis置为map[s][i]
12     memset(flag,false,sizeof(flag));
13     flag[s]=true;                            //将起点加入集合
14     for(i=1;i<n;i++){                        //依旧进行n-1次迭代,每次找到不在集合的最小边
15         md=INF;
16         for(j=1;j<=n;j++){
17             if(!flag[j]&&dis[j]<md){
18                 md=dis[j];
19                 temp=j;
20             }
21         }
22         flag[temp]=true;                      //将找到的最小边的点加入集合
23         total+=md;                            //并将这个边的权值加到total中
24         for(j=1;j<=n;j++)                     //松弛操作,注意与最短路不同
25             if(!flag[j]&&dis[j]>map[temp][j])
26                 dis[j]=map[temp][j];
27     }
28     return total;
29 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
下面是最短路的bellmen-ford算法,与dijkstra不同,bellman-ford可以运用于有负权值的图,不过复杂度很高,O(VE )... 慎用~(可以用SPFA,但是那个算法我掌握的不是很好:D)
Bellman-ford算法同样是对每条边进行N-1次松弛,当有权值为负时,对所有边进行N-1次松弛,如果dis还能更新,说明有负环。
Bellman-ford模板:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define INF 0x1f1f1f1f
 4 #define MAX 102
 5 #define MAXM 20008
 6 
 7 int dist[MAX];
 8 
 9 struct Edge{             //边结构体定义 
10     int u, v, w;
11     Edge(){}
12     Edge(int a, int b, int c):u(a), v(b), w(c){}
13 }edge[MAXM];
14 
15 int bellman_ford(int n, int m, int s)   //n个点、m条边、s为起点 
16 {
17     memset(dist, 0x1fsizeof(dist));    //初始化距离很大 
18     dist[s] = 0;
19     int i, j, u, v, f;
20     for (i = 1; i < n; ++i)         //迭代 n - 1 次,对每条边进行n-1次松弛
21     {
22            f = 0;
23          for (j = 0; j < m; ++j)
24            {
25          u = edge[j].u;
26          v = edge[j].v;
27              if (dist[v] > dist[u] + edge[j].w)  // 松弛操作 
28                 {
29              dist[v] = dist[u] + edge[j].w;
30                        f = 1;
31          }
32          }
33          if (!f) return 1;          //如果其中一次迭代没改变,停止
34     }
35     for(j = 0; j < m; ++j)     //再进行一次迭代 
36     {
37          u = edge[j].u;
38          v = edge[j].v;
39          if (dist[v] > dist[u] + edge[j].w)    //若还能松弛, 则存在负环 
40             return -1;                    //存在负环返回 -1 
41     }
42     return 1;       //没有负环返回 1 
43 }
算法结束后dist数组已经是最短路径。

posted on 2010-04-30 18:54 M.J 阅读(1968) 评论(1)  编辑 收藏 引用

评论

# re: 【图论】最短路和最小生成树  回复  更多评论   

太棒了
2014-02-07 17:01 | 杨玉飞

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理