用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 ;
}