Book 最短路算法

用HDU2544整理一下最近学的最短路算法

1.Dijkstra算法

原理：集合S表示已经找到最短路径的点，d[]表示当前各点到源点的距离

初始时，集合里面只有源点，当每个点u进入集合S时，用d[u]+w[u][v]更新距离

再重复这个步骤，选取S外所有点中d[]最小的进入集合

直到所有的点都进入S集合

局限性：图的边权必须为正

复杂度：O(V*V),堆优化（（E+V）logV）

(1)用邻接矩阵实现

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int w[maxn][maxn],d[maxn],used[maxn];

 int n,m;

 void dijkstra(int s){

     memset(used,,sizeof(used));

     for(int i=;i<=n;i++) d[i]=INF;

     d[s]=;

     for(int k=;k<=n;k++){

         int p,m=INF;

         for(int i=;i<=n;i++) if(!used[i]&&d[i]<m) m=d[p=i];

         used[p]=;

         for(int i=;i<=n;i++) d[i]=min(d[i],d[p]+w[p][i]);

     }

 }

 int main(){

     int a,b,c;

     while(scanf("%d %d",&n,&m)!=EOF&&n&&m){

         for(int i=;i<=n;i++){

             for(int j=;j<=n;j++){

                 if(i==j) w[i][j]=;

                 else w[i][j]=INF;

             }

         }

         for(int i=;i<=m;i++){

             scanf("%d %d %d",&a,&b,&c);

             w[a][b]=w[b][a]=c;

         }

         dijkstra();

         printf("%d\n",d[n]);

     }

     return ;

 }

(2)用邻接表实现

注意记得每次调用dijkstra()时，first[]置为-1

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[maxn],used[maxn],firstt[maxn],nextt[maxn];

 int n,m,ecnt;

 struct edge{

     int v,cost;

 } e[maxn];

 void dijkstra(int s){

     memset(used,,sizeof(used));

     for(int i=;i<=n;i++) d[i]=INF;

     d[s]=;

     for(int k=;k<=n;k++){

         int p,m=INF;

         for(int i=;i<=n;i++) if(!used[i]&&d[i]<m) m=d[p=i];

         used[p]=;

         for(int i=firstt[p];i!=-;i=nextt[i]){

             int v=e[i].v;

             if(d[v]>d[p]+e[i].cost)

             d[v]=d[p]+e[i].cost;

         }

     }

 }

 void addedges(int u,int v,int w){

     nextt[++ecnt]=firstt[u];

     e[ecnt].v=v;

     e[ecnt].cost=w;

     firstt[u]=ecnt;

 }

 int main(){

     int a,b,c;

     while(scanf("%d %d",&n,&m)!=EOF&&n&&m){

         ecnt=;

         memset(firstt,-,sizeof(firstt));

         for(int i=;i<=m;i++){

             scanf("%d %d %d",&a,&b,&c);

             addedges(a,b,c);

             addedges(b,a,c);

         }

         dijkstra();

         printf("%d\n",d[n]);

     }

     return ;

 }

(3)堆（优先队列）优化
参看紫书上的解释，STL中的pair是专门将两个类型捆绑起来的，

而且pair定义了它自己的排序规则，先比较第一维，相等时才比较第二维，所以需要按照(d[i],i)的顺序组合。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 #define MP(a,b) make_pair(a,b)

 using namespace std;

 typedef long long LL;

 typedef pair<int,int> pii;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[maxn],firstt[maxn],nextt[maxn];

 int n,m,ecnt;

 struct edge{

     int v,cost;

     friend bool operator < (edge a,edge b){

         return a.cost>b.cost;

     }

 }e[maxn];

 void addedges(int u,int v,int c){

     nextt[++ecnt]=firstt[u];

     e[ecnt].v=v;

     e[ecnt].cost=c;

     firstt[u]=ecnt;

 }

 void dijkstra(int s){

     priority_queue<pii> pq;

     for(int i=;i<=n;i++) d[i]=INF;

     d[s]=;

     pq.push(MP(d[s],));

     while(!pq.empty()){

         pii x=pq.top();pq.pop();

         if(d[x.second]<x.first) continue;//当前状态没有现在dis[]数组里面的优，所以不用再继续判断下去

         for(int i=firstt[x.second];i!=-;i=nextt[i]){

             int v=e[i].v;

             if(d[v]>d[x.second]+e[i].cost){

                 d[v]=d[x.second]+e[i].cost;

                 pq.push(MP(d[v],v));

             }

         }

     }

 }

 int main(){

     int a,b,c;

     while(scanf("%d %d",&n,&m)!=EOF&&n&&m){

         memset(firstt,-,sizeof(firstt));

         ecnt=;

         for(int i=;i<=m;i++){

             scanf("%d %d %d",&a,&b,&c);

             addedges(a,b,c);

             addedges(b,a,c);

         }

         dijkstra();

         printf("%d\n",d[n]);

     }

     return ;

 }

(4)用vector存图实现的

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[maxn];

 typedef struct edge{

     int to,distance;

     edge(){}

     edge(int to,int distance) :to(to),distance(distance){}

 };

 typedef pair<int,int> P;

 vector<edge> G[maxn];

 int n,m,k;

 void dijkstra(int s){

     priority_queue<P,vector<P> ,greater<P> > q;

     for(int i=;i < n;i++) d[i]=INF;

     d[s]=;

     q.push(P(,s));

     while(!q.empty()){

         P p=q.top();q.pop();

         int v=p.second;

         if(d[v]<p.first) continue;

         for(int i=;i<G[v].size();i++){

             edge e=G[v][i];

             if(d[e.to] > d[v]+e.distance){

                 d[e.to] = d[v]+e.distance;

                 q.push(P(d[e.to],e.to));

             }

         }

     }

 }

 int main(){

     while(scanf("%d %d",&n,&m)!=EOF){

         if(n==&&m==) break;

             for(int i=;i<n;i++) G[i].clear();

         while(m--){

             int u,v,w;

             scanf("%d %d %d",&u,&v,&w);

             u--;v--;

             G[u].push_back(edge(v,w));

             G[v].push_back(edge(u,w));

         }

         dijkstra();

         printf("%d\n",d[n-]);

     }

     return ;

 }

2.Bellman_Ford算法

原理：对于图G(V,E),Bellman_Ford是对整个图进行V-1次松弛，每次松弛检查每条边，如果d[v]>d[u]+cost,那么则更新d[v]

应用：可以用来判断负环，如果没有负权回路的话，那么任意两点间的路径最多经过n-2个点，

即最多松弛n-1次，如果有负权回路，那么第n次松弛操作仍然会成功。

复杂度：O(VE)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int d[maxn];

 int n,m,ecnt;

 struct edge{

     int u,v,cost;

 } e[maxn];

 void addedges(int u,int v,int c){

     e[++ecnt].u=u;

     e[ecnt].v=v;

     e[ecnt].cost=c;

 }

 void Bellman_Ford(int s){

     for(int i=;i<=n;i++) d[i]=INF;

     d[s]=;

     for(int i=;i<n;i++){

         for(int j=;j<=ecnt;j++){

             if(d[e[j].v]>d[e[j].u]+e[j].cost)

             d[e[j].v]=d[e[j].u]+e[j].cost;

         }

     }

 }

 int main(){

     int a,b,c;

     while(scanf("%d %d",&n,&m)!=EOF&&n&&m){

         ecnt=;

         for(int i=;i<=m;i++){

             scanf("%d %d %d",&a,&b,&c);

             addedges(a,b,c);

             addedges(b,a,c);

         }

         Bellman_Ford();

         printf("%d\n",d[n]);

     }

     return ;

 }

巴特西

Book 最短路算法

最新文章

热门文章