hdu2544 最短路 几种最短路算法实现

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

Floyd-Warshall算法：时间复杂度O（V^3）一般不用 算法模板

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAX_V = 110; const int INF = 0x3f3f3f3f; int d[MAX_V][MAX_V];//d[u][v]表示边e=(u,v)的权值(不存在时设为INF,不过d[i][i]=0) int V,m; //顶点和边数 void warshall_floyd() { for(int k = 0;k < V;k ++){ for(int i = 0;i < V;i ++) for(int j = 0;j < V;j ++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } int main() { int a,b,c; while(scanf("%d%d", &V, &m) && (m || V)){ memset(d, INF, sizeof(d)); while(m --){//存边 scanf("%d%d%d",&a,&b,&c); d[a-1][b-1] = c; d[b-1][a-1] = c; } warshall_floyd();//以p中位置为0的顶点为源点，球其到其余各顶点的最短距离 printf("%d\n", d[0][V - 1]); } return 0; }

dijkstra算法：时间复杂度O（V^2） 算法模板

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int MAX_V = 110; const int INF = 0x3f3f3f3f; int cost[MAX_V][MAX_V]; //cost[u][v]表示边e=(u,v)的权值，(不存在时这条边设为INF) int d[MAX_V]; //顶点s出发的最短距离 bool used[MAX_V]; //已经使用过的图 int V,m; //定点数 //求从s出发到各个顶点的最短距离 void dijkstra(int s){ fill(d, d + V, INF); fill(used, used + V, false); d[s] = 0; while(true){ int v = -1; //从尚未使用过的顶点中选择一个距离最小的顶点 for(int u = 0;u < V;u ++){ if(!used[u] && (v == -1 || d[u] < d[v])) v = u; } if(v == -1) break; used[v] = true; //标记为使用 for(int u = 0;u < V;u ++){//更新d[]中的值 d[u] = min(d[u], d[v] + cost[v][u]); } } } int main() { int a,b,c; while(scanf("%d%d", &V, &m) && (m || V)){ memset(cost, INF, sizeof(cost)); while(m --){//存边 scanf("%d%d%d",&a,&b,&c); cost[a-1][b-1] = c; cost[b-1][a-1] = c; } dijkstra(0);//以p中位置为0的顶点为源点，球其到其余各顶点的最短距离 printf("%d\n", d[V - 1]); } return 0; } 优先队列优化后的dijkstra算法：时间复杂度O（E） #include <stdio.h> #include <string.h> #include <algorithm> #include <utility> #include <queue> using namespace std; const int INF = 0X3F3F3F3F; const int MAX_V = 110; struct edge { //cost代表一个点到to这个点的权值 int to, cost; }; typedef pair<int ,int > P; //first为最短距离，second为顶点序号 int V,m; //顶点和边的数 vector<edge > G[MAX_V]; //G[i]存放的是第i个点到 其他点的序号和权值 int d[MAX_V]; //d[i]存放的是s到i的最短距离 void dijkstra_pri(int s) { //通过指定greater<P>参数，堆按照first从小到大的顺序取出值 priority_queue<P, vector<P>, greater<P> > que; fill(d, d+V, INF); d[s] = 0; que.push(P(0,s)); //把第一个点权值和序号存入 while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(p.first > d[v]) continue; //除去存入的相同序号不同权值 for(int i = 0;i < G[v].size();i ++){ edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { int a,b; edge e; while(scanf("%d%d", &V, &m) && (m || V)){ while(m --){ //注意从0开始存 scanf("%d%d%d",&a,&b,&e.cost); e.to = b-1; G[a-1].push_back(e); e.to = a-1; G[b-1].push_back(e); } dijkstra_pri(0); printf("%d\n",d[V-1]); while(V --) G[V].clear(); //清空G数组 } return 0; }

spfa算法：复杂度O(VE)    算法模板

#include <stdio.h> #include <string.h> #include <algorithm> #include <utility> #include <queue> using namespace std; const int INF = 0x3f3f3f3f; const int MAX_V = 110; struct edge { //cost代表一个点到to这个点的权值 int to, cost; }; int V, m; //顶点数,边数 vector<edge> G[MAX_V]; //G[i]存放的是第i个点到 其他点的序号和权值 int d[MAX_V]; //d[i]存放的是指定节点s到i的最短距离 bool vis[MAX_V]; //vis[i]标记第i个顶点是否在队列 void spfa(int s) { queue<int > que; //存顶点 fill(d, d+V, INF); //初始化d fill(vis, vis+V, false); d[s] = 0; que.push(s); //把第一个点序号存入 while(!que.empty()) { int i, v = que.front(); que.pop(); vis[v] = false; //v不在队列中 for(int i = 0;i < G[v].size();i ++){ edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; if(!vis[e.to]){ //如果e.to不在队列中 que.push(e.to); vis[e.to] = true; } } } } } int main() { int a,b; edge e; while(scanf("%d%d", &V, &m) && (m || V)){ while(m --){ //注意从0开始存 scanf("%d%d%d",&a,&b,&e.cost); e.to = b-1; G[a-1].push_back(e); e.to = a-1; G[b-1].push_back(e); } spfa(0); printf("%d\n",d[V-1]); while(V --) //清空G数组 G[V].clear(); } return 0; }