? ? ? ?本文是最短路徑算法整理的第二篇，想閱讀第一篇的朋友能夠點(diǎn)擊下面鏈接：

? ? ? ? http://blog.csdn.net/hjd_love_zzt/article/details/26739593

? ? ? ?這一篇博客繼續(xù)以一些OJ上的題目為載體，整理一下最短路徑算法。會(huì)陸續(xù)的更新。。。

? ? ? 1、HDU 2544

? ? ? 題目與分析：這道題抽象一下，還是：“求a到b的最短路徑”。。所須要的基本條件是：點(diǎn)數(shù)、邊數(shù)、起點(diǎn)、終點(diǎn)

? ? ? 下面給出floyd、dijkstra、bellmanford三種最短路徑算法關(guān)于這道題的解法：

? ? ??

? ? ?1）floyd

? ? ?

/** HDU_2544.cpp** Created on: 2014年5月31日* Author: Administrator*/#include <iostream> #include <cstdio>using namespace std;const int maxn = 105; const int inf = 10000005;int e[maxn][maxn]; int n;void initial(){int i;int j;for(i = 1 ; i <= n ; ++i){for(j = 1 ; j <= n ; ++j){if(i == j){e[i][j] = 0;}else{e[i][j] = inf;}}} }void floyd(){int k;int i;int j;for(k = 1 ; k <= n ; ++k){for(i = 1 ; i <= n ; ++i){for(j = 1 ; j <= n ; ++j){if(e[i][j] > e[i][k] + e[k][j]){e[i][j] = e[i][k] + e[k][j];}}}} }int main(){int m;while(scanf("%d%d",&n,&m),n||m){initial();int i;for(i = 1 ; i <= m ; ++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);e[a][b] = e[b][a] = c;}floyd();printf("%d\n",e[1][n]);}return 0; }

? ?2）dijkstra

/** HDU_2544.cpp** Created on: 2014年5月31日* Author: Administrator*/#include <iostream> #include <cstdio>using namespace std;const int maxn = 105; const int inf = 10000005;int n; int s[maxn]; int dis[maxn]; int map[maxn][maxn];int target;int dijkstra(int v){int i;for(i = 1 ; i <= n ; ++i){s[i] = 0;dis[i] = map[v][i];}// dis[v] = 0;//事實(shí)上上面的操作已經(jīng)包括這個(gè)意思了int j;for(i = 1 ; i < n ; ++i){int min = inf;int pos;for(j = 1 ; j <= n ; ++j){if(!s[j] && dis[j] < min){min = dis[j];pos = j;}}s[pos] = 1;for(j = 1 ; j <= n ; ++j){if(dis[j] > dis[pos] + map[pos][j]){dis[j] = dis[pos] + map[pos][j];}}}return dis[target]; }int main(){int m;while(scanf("%d%d",&n,&m),n||m){int i;int j;for(i = 1 ; i <= n ; ++i){for(j = 1 ; j <= n ; ++j){if(i == j){map[i][j] = 0;}else{map[i][j] = inf;}}}for(i = 1 ; i <= m ; ++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);map[a][b] = map[b][a] = c;}target = n;int result = dijkstra(1);printf("%d\n",result);}return 0; }

3）bellmanford

/** HDU_2544.cpp** Created on: 2014年5月31日* Author: Administrator*/#include <iostream> #include <cstdio>using namespace std;struct Edge{int u;int v;int weight; };const int maxn = 105; const int maxm = 10005; const int inf = 1000005;Edge edge[maxm]; int dis[maxn];int n,m; int source;bool bellmanford(){int i;int j;for(i = 1 ; i <= n ; ++i){dis[i] = inf;}dis[source] = 0;for(i = 1 ; i <= n ; ++i){for(j = 1 ; j <= m ; ++j){if(dis[edge[j].v] > dis[edge[j].u] + edge[j].weight){dis[edge[j].v] = dis[edge[j].u] + edge[j].weight;}if(dis[edge[j].u] > dis[edge[j].v] + edge[j].weight){dis[edge[j].u] = dis[edge[j].v] + edge[j].weight;}}}for(j = 1 ; j <= m ; ++j){if(dis[edge[j].v] > dis[edge[j].u] + edge[j].weight){return false;}}return true; }int main(){while(scanf("%d%d",&n,&m),n||m){int i;for(i = 1 ; i <= m ; ++i){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].weight);}source = 1;bellmanford();printf("%d\n",dis[n]);}return 0; }

2、HDU 2066 一個(gè)人的旅行

題目分析：

? ? ?這一道題還是最短路徑問題。可是有下面幾個(gè)不同點(diǎn)：

? ? ?1》與尋常的給出點(diǎn)數(shù)、邊數(shù)、起點(diǎn)、終點(diǎn)不同。這道題給出了多個(gè)起點(diǎn)和終點(diǎn)、而且沒有給出點(diǎn)數(shù)

? ? ?

這道題我用floyd做的時(shí)候TLE了，所以臨時(shí)僅僅給出dijkstra解法的版本號(hào)

/** HDU_2066.cpp** Created on: 2014年6月1日* Author: Administrator*/#include <iostream> #include <cstdio>using namespace std;const int maxn = 1010; const int inf = 100000005;int s[1015]; int dis[1015]; int map[1015][1015];int start, d;int from[maxn]; int want[maxn];int dijkstra(int v) {int i;for (i = 1; i <= maxn; ++i) {//由于題目沒有給出點(diǎn)數(shù),所以每一次都所有掃一遍s[i] = false;dis[i] = map[v][i];}for (i = 1; i < maxn; ++i) {int min = inf;int pos;int j;for (j = 1; j <= maxn; ++j) {if (!s[j] && dis[j] < min) {min = dis[j];pos = j;}}s[pos] = 1;for (j = 1; j <= maxn; ++j) {if (!s[j] && dis[j] > dis[pos] + map[pos][j]) {dis[j] = dis[pos] + map[pos][j];}}} //到這里就已經(jīng)算出以點(diǎn)v為起點(diǎn)的最短路徑的情況了....這時(shí)候再遍歷一下ends[]，便能求出v到ends[]中哪個(gè)終點(diǎn)近期了int minn = inf;for (i = 0; i < d; ++i) {//用來解決多終點(diǎn)的問題int temp = dis[want[i]];if (minn > temp) {minn = temp;}}return minn; }int main() {int t;while (scanf("%d%d%d", &t, &start, &d) != EOF) {int i;int j;for (i = 1; i <= maxn; ++i) {for (j = 1; j <= maxn; ++j) {if (i == j) {map[i][j] = map[j][i] = 0;} else {map[i][j] = map[j][i] = inf;}}}for (i = 1; i <= t; ++i) {int a, b, c;scanf("%d%d%d", &a, &b, &c);if (map[a][b] > c) {map[a][b] = map[b][a] = c;}}for (i = 0; i < start; ++i) {scanf("%d", &from[i]);}for (i = 0; i < d; ++i) {scanf("%d", &want[i]);}int result = inf;for (i = 0; i < start; ++i) {//用來解決多起點(diǎn)的問題int temp = dijkstra(from[i]);if (result > temp) {result = temp;}}printf("%d\n", result);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/4297716.html

總結(jié)

以上是生活随笔為你收集整理的最短路径算法整理（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。