首页 > 代码库 > 图论算法----最短路

图论算法----最短路

2024-07-07 14:16:28   224人阅读

经典算法

单源最短路：

1.Bellman_ford（可判负环，可有负边）

d[i]表示起点S到i的最短路，那么d[i]=min{d[j]+w[j][i]}且存在j->i的边代价为w[j][i]

经过证明如果不存在负圈最多通过V-1次松弛就可以完成复杂度O(V*E)(V为结点数，E为边数)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 50010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 struct edge{
14     int from,to,w;
15     edge(){}
16     edge(int _u,int _v,int _w){
17         from=_u,to=_v,w=_w;
18     }
19 };
20 edge G[maxm];
21 int V,E;
22 void addedge(int u,int v,int w){
23     G[E++]=edge(u,v,w);
24 }
25 int d[maxn];
26 int n,m;
27 //d[i] = min{d[j]+w[j][i]} {j->i}
28 void bellman_ford(int s){
29     V=n;
30     for(int i=0;i<V;++i)d[i]=INF;
31     d[s]=0;
32     while(1){
33         bool flag =false;
34         for(int i=0;i<E;++i){
35             edge e = G[i];
36             if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.w){
37                 d[e.to] = d[e.from]+e.w;
38                 flag = true;
39             }
40         }
41         if(!flag)break;
42     }
43 }
44 int main (){
45     while(scanf("%d%d",&n,&m)!=EOF){
46         if(n==0&&m==0)break;
47         int u,v,w;
48         E=0;
49         for(int i=0;i<m;++i){
50             scanf("%d%d%d",&u,&v,&w);
51             addedge(u-1,v-1,w);
52             addedge(v-1,u-1,w);
53         }
54         bellman_ford(0);
55         printf("%d\n",d[n-1]);
56     }
57 }
View Code

判负环：看一下是不是多于V-1次松弛，如果有则存在负环

 1 bool HaveNagativeLoop(){
 2     memset(d,0,sizeof(d));
 3     for(int i=0;i<V;++i){
 4         for(int j=0;j<E;++j){
 5             edge e = G[j];
 6             if(d[e.to]>d[e.from]+e.w){
 7                 d[e.to] = d[e.from]+e.w;
 8                 if(i==V-1)return true;
 9             }
10         }
11     }
12     return false;
13 }
View Code

 2.dijkstra(无负边)

对于上述的d[i]=min{d[j]+w[j][i]}如果d[j]当前值不是d[j]能达到的最小值那么显然在后面d[i]还将更新，如何避免这种情况

选择d[j]已经是最小，即S->j的最短距离不再更新，如何选取？每次选择距离最短且未被使用的结点，用这个结点对其他节点进行松弛复杂度O(V*V)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 1010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 //d[i]=min{d[j]+w[j][i]} {d[j]已经不再更新}
14 //每次找最小d[j]然后松弛
15 int G[maxn][maxn];
16 int d[maxn];
17 bool used[maxn];
18 int V;
19 void dijksta(int s){
20     for(int i=0;i<V;++i){
21         used[i]=false;
22         d[i]=INF;
23     }
24     d[s]=0;
25     while(1){
26         int v =-1;
27         for(int i=0;i<V;++i){
28             if(!used[i]&&(v==-1||d[i]<d[v]))v=i;
29         }
30         if(v==-1)break;
31         used[v]=true;
32         for(int i=0;i<V;++i){
33             d[i]=min(d[i],d[v]+G[v][i]);
34         }
35     }
36 }
37 void init(int n){
38     V = n;
39     for(int i=0;i<V;++i){
40         for(int j=0;j<V;++j){
41             if(i==j)G[i][j]=0;
42             else G[i][j]=INF;
43         }
44     }
45 }
46 int main (){
47     int n,m;
48     while(scanf("%d%d",&n,&m)!=EOF){
49         if(n==0&&m==0)break;
50         int u,v,w;
51         init(n);
52         for(int i=0;i<m;++i){
53             scanf("%d%d%d",&u,&v,&w);
54             G[u-1][v-1]=w;
55             G[v-1][u-1]=w;
56         }
57         dijksta(0);
58         printf("%d\n",d[n-1]);
59     }
60 }
View Code

 来优化一下上面的算法，每次需要选择最短的一个结点，这个可以使用一个优先队列来维护当前所有边里面权值最小的边，所以算法复杂度变为O(V*log(E))

使用邻接表存储图比较容易写

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 1010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 struct edge {
14     int to,w;
15     edge(){}
16     edge(int _to,int _w){
17         to=_to;w=_w;
18     }
19 };
20 typedef pair<int,int> P;
21 int V;
22 vector<edge> G[maxn];
23 int d[maxn];
24 void dijkstra(int s){
25     priority_queue<P,vector<P>,greater<P> >q;
26     for(int i=0;i<V;++i)d[i]=INF;
27     d[s]=0;
28     q.push(P(d[s],s));
29     while(!q.empty()){
30         P p = q.top();
31         q.pop();
32         int v = p.second;
33         if(d[v]<p.first)continue;
34         for(int i=0;i<G[v].size();++i){
35             edge e = G[v][i];
36             if(d[e.to]>d[v]+e.w){
37                 d[e.to]=d[v]+e.w;
38                 q.push(P(d[e.to],e.to));
39             }
40         }
41     }
42 }
43 int main (){
44     int n,m;
45     while(scanf("%d%d",&n,&m)!=EOF){
46         for(int i=0;i<n;++i)G[i].clear();
47         V=n;
48         if(n==0&&m==0)break;
49         int u,v,w;
50         for(int i=0;i<m;++i){
51             scanf("%d%d%d",&u,&v,&w);
52             G[u-1].push_back(edge(v-1,w));
53             G[v-1].push_back(edge(u-1,w));
54         }
55         dijkstra(0);
56         printf("%d\n",d[n-1]);
57     }
58 }
View Code

 3.floyd(任意两点的最短路，可有负边)

dp的思想   d[k+1][i][j]表示从0~k 里面选择中间结点从i到j的最短距离 那么当k为-1时d[0][i][j]=w[i][j] 

考虑如何转移 从0~k-1中间选到0~k中选新的方案有两种情况：

不经过第k个结点 那么 d[k+1][i][j]=d[k][i][j]

经过第k个结点   那么d[k+1][i][j] = d[k][i][k]+d[k][k][j]

则方程为d[k+1][i][j]=min{ d[k][i][j]，d[k][i][k]+d[k][k][j]}

可以使用滚动数组来优化空间，由于d[k+1][][]只与d[k][][]有关，所以只要保证k是从小到大枚举的就可以节省以为空间，复杂度为O(V*V*V)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include <queue>
 8 #include<vector>
 9 #define maxn 1010
10 #define maxm 100010
11 #define INF 0x3fffffff
12 using namespace std;
13 int d[maxn][maxn];
14 int V;
15 void init(int n){
16     V=n;
17     for(int i=0;i<V;++i){
18         for(int j=0;j<V;++j){
19             if(i==j)d[i][j]=0;
20             else d[i][j]=INF;
21         }
22     }
23 }
24 void floyd(){
25     for(int k=0;k<V;++k){
26         for(int i=0;i<V;++i){
27             for(int j=0;j<V;++j){
28                 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
29             }
30         }
31     }
32 }
33 int main (){
34     int n,m;
35     while(scanf("%d%d",&n,&m)!=EOF){
36         if(n==0&&m==0)break;
37         int u,v,w;
38         init(n);
39         for(int i=0;i<m;++i){
40             scanf("%d%d%d",&u,&v,&w);
41             d[u-1][v-1]=w;
42             d[v-1][u-1]=w;
43         }
44         floyd();
45         printf("%d\n",d[0][n-1]);
46     }
47 }
View Code

 


联系
我们