Floyd Dijkstra Bellman-Ford spfa 四种最短路经典算法汇总

最短路

    

     2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
    

    

     3
2
    

No. 1 Floyd

#include <bits/stdc++.h>#define endl "\n"#define inf 0x7fffffff
using namespace std;const int MAXN = 100 + 7;int n, m;
int dis[MAXN][MAXN];void Init() {for(int i = 0; i <= n; ++i) {for(int j = 0; j <= n; ++j) {i == j ? dis[i][j] = 0 : dis[i][j] = inf;}}
}int main()
{ios::sync_with_stdio(false);while(cin >> n >> m) {if(!n && !m) break;Init();int u, v, w;for(int i = 1; i <= m; ++i) {cin >> u >> v >> w;dis[u][v] = min(w, dis[u][v]);dis[v][u] = min(w, dis[v][u]);}/***************************************        Floyd O(n^3)*      三行情书, for 循环中i, j, k*      顺序不能变（k）*      本质是动态规划，枚举状态，转移**************************************/for(int k = 1; k <= n; ++k) {for(int i = 1; i <= n; ++i) {for(int j = 1; j <= n; ++j) {if(dis[i][k] < inf && dis[k][j] < inf && dis[i][j] > dis[i][k] + dis[k][j]) {dis[i][j] = dis[i][k] + dis[k][j];}}}}cout << dis[1][n] << endl;}return 0;
}

No. 2 Dijkstra

/***********************************************************           最短路Dijkstra算法  O(n^2)*   适用于求单源最短路，不适合带有负权的情形*   算法思想：从原点出发，每次找一个源点能到达的最短路*          径并找到该点将其标号，再从源点开始将所有*          点的距离依照*             dis[j] > dis[index] + gra[index][j]*          更新*   基于：最短路的子路也一定是最短路*********************************************************/#include <bits/stdc++.h>#define endl "\n"#define inf 0x7ffffff
using namespace std;const int MAXN = 100 + 7;
int n, m;
int dis[MAXN], vis[MAXN], gra[MAXN][MAXN];void Init() {for(int i = 0; i <= n; ++i) {vis[i] = 0;for(int j = 0; j <= n; ++j) {gra[i][j] = inf;}}
}void Dijkstra(int u) {int mindis = inf, index;vis[u] = 1, dis[u] = 0;for(int i = 1; i <= n; ++i) {dis[i] = gra[u][i];}for(int i = 1; i <= n; ++i) {mindis = inf;for(int j = 1; j <= n; ++j) {if(!vis[j] && dis[j] < mindis) {mindis = dis[j];index = j;}}vis[index] = 1;for(int j = 1; j <= n; ++j) {if(!vis[j] && dis[index] + gra[index][j] < dis[j]) {dis[j] = dis[index] + gra[index][j];}}}
}int main()
{ios::sync_with_stdio(false);while(cin >> n >> m) {if(!n && !m) break;Init();int u, v, w;for(int i = 0; i < m; ++i) {cin >> u >> v >> w;gra[u][v] = min(gra[u][v], w);gra[v][u] = min(gra[v][u], w);}Dijkstra(1);cout << dis[n] << endl;}return 0;
}

/********************************************************              Bellman-Ford  O(V*E)*      使用条件更广泛，可处理带环，负权，负环的问题*          可求得单元最短路并求出路径反向输出*      算法伪码：*      BELLMAN-FORD(G, w, s)*      1  INITIALIZE-SINGLE-SOURCE(G, s)*      2  for i ← 1 to |V[G]| - 1      // 最多n-1次松弛*      3       do for each edge (u, v) ∈ E[G]*      4              do RELAX(u, v, w)*      5  for each edge (u, v) ∈ E[G]*      6       do if d[v] > d[u] + w(u, v)*      7             then return FALSE*      8  return TRUE*      算法思想：*      首先初始化所有dis[i] = inf*      对于每一条边e(u, v)，*      如果*              dis[u] + w(u, v) < dis[v]*      则令*              dis[v] = dis[u]+w(u, v)*      w(u, v)为边e(u,v)的权值；*      为了检测图中是否存在负环路，即权值之和小于0的环路。*      松弛完成后，对于每一条边e(u, v)，如果存在*              dis[u] + w(u, v) < dis[v]的边，*      则图中存在负环路，即是说该图无法求出单源最短路径。*      否则数组dis[n]中记录的就是源点s到各顶点的最短路径长度。**      PS：无向图可用反向建边的方式*******************************************************/#include <bits/stdc++.h>#define endl "\n"#define inf 0x7fffffff
using namespace std;const int MAXN = 100 + 7;struct Edge {int u, v, w;
}edge[MAXN * MAXN * 2];int dis[MAXN], n, m;void Init() {for(int i = 1; i <= 2*m; ++i) {edge[i].w = inf;}for(int i = 0; i <= n; ++i) {dis[i] = inf;}
}bool BellmanFord(int u) {dis[u] = 0;for(int i = 1; i < n; ++i) {for(int j = 1; j <= 2*m; ++j) {if(dis[edge[j].u] < inf) {dis[edge[j].v] = min(dis[edge[j].v], dis[edge[j].u] + edge[j].w);}}}bool flag = true;for(int i = 1; i <= 2*m; ++i) {if(dis[edge[i].v] > dis[edge[i].u] + edge[i].w) {flag = false;break;}}return flag;
}int main()
{ios::sync_with_stdio(false);while(cin >> n >> m) {if(!n && !m) break;Init();int u, v, w;for(int i = 1; i <= m; ++i) {cin >> u >> v >> w;edge[i].u = u;edge[i].v = v;//cout << edge[i].w << endl;edge[i].w = min(w, edge[i].w);edge[i+m].u = v;edge[i+m].v = u;edge[i+m].w = min(w, edge[i+m].w);}BellmanFord(1);cout << dis[n] << endl;}return 0;
}

/********************************************************              spfa   O(k * E)  (k 一般 <= 2)*      算法思想：spfa其实就是改进的Bellman-Ford*          这里将由i发出的能直接到达的点存放在*          link[i]里，用bfs进行松弛操作，将在队*          列里面的点标记，每次将队首元素出列，*          根据link[v]遍历与v连接的点并进行松弛*          操作，遍历完所有点后就得到了最短路（存在）*          再开一个cnt数组，cnt[i]表示i进入队列*          的次数，当i>n时，存在负环，无最短路* #define endl "\n"#define inf 0x7fffffff          // 注意inf的条件
using namespace std;const int MAXN = 100 + 7;
int gra[MAXN][MAXN], vis[MAXN], dis[MAXN], cnt[MAXN];
vector< vector<int> > link(MAXN);     // link[i]中存由i能直接到达的点的编号
int n, m;
void Init() {for(int i = 0; i < MAXN; ++i) { // 多重vector不能直接link.clear()link[i].clear();}for(int i = 0; i <= n; ++i) {dis[i] = inf;cnt[i] = vis[i] = 0;}for(int i = 0; i <= n; ++i) {for(int j = 0; j <= n; ++j) {i == j ? gra[i][j] = 0 : gra[i][j] = inf;}}
}bool spfa(int u) {dis[u] = 0;cnt[u] = vis[u] =  1;             // vis代表在不在队列内queue<int> q;q.push(u);while(!q.empty()) {int v = q.front();vis[v] = 0;     // 每次队首元素出队列就将vis[v]置零q.pop();for(int i = 0; i < link[v].size(); ++i) {       // 由v指向的所有点进行松弛操作if(dis[v] < inf && dis[link[v][i]] > dis[v] + gra[v][link[v][i]]) {dis[link[v][i]] = dis[v] + gra[v][link[v][i]];if(!vis[link[v][i]]) {q.push(link[v][i]);vis[link[v][i]] = 1;cnt[link[v][i]]++;if(cnt[link[v][i]] > n) return false;   // 存在负环}}}}return true;
}int main()
{ios::sync_with_stdio(false);while(cin >> n >> m) {if(!n && !m) break;Init();int u, v, w;for(int i = 1; i <= m; ++i) {cin >> u >> v >> w;gra[u][v] = min(w, gra[u][v]);          // 无向图反向建边gra[v][u] = min(w, gra[v][u]);link[u].push_back(v);link[v].push_back(u);}spfa(1);cout << dis[n] << endl;}return 0;
}