文章目录
-
- 概述
- Dijkstra算法
- Bellman-Ford算法和SPFA算法
- Floyd算法
概述
\qquad 本文把求图的最短路径的几种方法综合阐述，已经列举出相应的练习题，以求透彻理解和熟练解决最短路径相关的问题。最短路径，就是求一条从起点到终点的路径，使得这条路径上所有边的边权之和最小。这三种方法分别是Dijkstra算法，Bellman-Frod算法和SPFA算法以及Floyd算法。
Dijkstra算法
这个算法适合解决：单源最短路劲问题。（即给定图G和起点s,通过算法得到s到达其他每个定点的最短距离。）
算法的基本思想：对图G(V,E)设置集合S,存放已被访问的顶点，然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点（记为u），访问并加入集合S.之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。
注意：该算法只适合所有边权都是非负数的情况，如果出现负数，那么该算法将会出错，最好使用SPFA算法。
关于这个算法的过程，算法笔记给了一个有趣的例子，大家可以先看一下。
好了，看完了例子，接下来是思考如何编码了。个人觉得编码就是写出数据结构使输入输出的信息以及中间处理时产生的可用的信息得以保存，并尽可能简单。为什么要保存，因为我们写代码，其实就是操纵的这些信息。那么对于这道题，首先，它是图，所以有邻接矩阵表示和邻接表表示两种情况。这两个任选一个，就可以表达出图了，之后就可以对其进行操作了。另外，本题还需要维护一个数组和变量。比如说是结点s到各个顶点的距离最大值数组，各个结点是否被访问数组（这个数组就实现了上面说的那个存放已访问元素的集合S以及未访问元素的集合V-S）等，这里如果一开始没法思考全，可以先写思考到的，等到编码的时候遇到了，再继续添加。等熟练了，大多数都是套路，就那么几个变量。
那么，这里图是全部代码的一个核心数据结构，围绕着它展开。他有邻接表和邻接矩阵两种表达。邻接矩阵时，它的时间复杂度在 O ( V 2 ) O(V^2) O(V2).邻接表时，它的复杂度在 O ( V 2 + E ) O(V^2+E) O(V2+E).
这是最短距离，那路径怎么求，其实还是加一个数组记录信息，无一例外，需要新的信息，就需要考虑增加新的数据结构或者是利用原来的数据结构，他们就是用来存储信息的。在这里，我们考虑到加入新的一个结点时，如果最短距离变小，那么该点的前驱就设置成u,意思就是说从u到v目前最短。就可以啦。
可是真实的考题，一般还会比这个稍微复杂一点，（就是说需要多定义几个数组的事！）一般呢，有三种变体：新增边权（比如说花费），新增点权（比如说每个城市能收集到的物资），直接问有多少条最短路径。下面来一一举例：
1.新增边权。
这是一个典型的最短路径的问题，并且求的只是最短距离。但是人家加了一个边权，就是题目中的风暴时间。好了，本题求的是单源最短路径，边权都是非负数，适合Dijkstra算法。
后来我觉得这道题是动态的边权。AC的代码：
#include <iostream>
using namespace std;
const int MAXV = 1000; //本题的顶点数为500，还不算大。
const int INF = 1000000000; //设INF是一个很大的数。
int g[MAXV][MAXV]; //图
bool vit[MAXV] = { false }; //记录是否访问
int d[MAXV]; //记录最短距离
struct node {
int qi1;
int end1;
};
node g1[MAXV][MAXV]; //记录风暴信息，看，就是加个数组的事。
void Dijkstra(int s,int n) {
d[s] = 0;
vit[s] = true;
for (int i = 1; i < n; i++) {
int u = -1; int MIN = INF;
for (int j = 1; j < n; j++) {
if(vit[j]==false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if (u == -1) { return; }
vit[u] = true;
for (int v = 1; v < n; v++) {
if (vit[v]==false&&g[u][v]!=0) {
//在这里需要单独更新一下边的权值，因为这里叠加了风暴的因素，因此是动态的权值。
if ((d[u] >= g1[u][v].qi1 - g[u][v]) && (d[u] <= g1[u][v].end1)) { g[u][v] = g1[u][v].end1 - d[u] + g[u][v]; }
else {}
if (d[u] + g[u][v] < d[v]) {
d[v] = d[u] + g[u][v];
}
}
}
}
}
int main() {
int N, M;
cin >> N >> M;
fill(d, d + MAXV, INF); //先置为最大值
for (int i = 0; i < M; i++) {
int a, b, c, d1, e;
cin >> a >> b >> c >> d1 >> e;
g[a][b] = g[b][a] = c;
g1[a][b].qi1 = d1;
g1[b][a].qi1 = d1;
g1[a][b].end1 = e;
g1[b][a].end1 = e;
//这个地方是先把与1相连的边，先给初始化。
if (a == 1) {
if (d1 > c) { d[b] = c;}
else { d[b] = e+c; }
}
if (b == 1) {
if (d1 > c) { d[a] = c; }
else { d[a] = e+c; } //权值就是它风暴结束的那一天+渡河需要的时间。
}
}
Dijkstra(1,N+1);
cout << d[N]+1;
return 0;
}
//输出最短路径
void DFS(int s,int n) { //s为起点，n为目标点
if (n == s) { //这是递归出口。
cout << s<<endl;
return;
}
DFS(s, pre[n]); //这个pre数组是在更新最短距离时更新的。
cout << n << endl;
/*
1.要把递归出口写在最前面。
2.要把在这一层的输出放在往后的层的输出的下面，因为下面的深层应该是先输出的。
这是关于递归的几点理解。
*/
}
更多的变种可参考这篇文章。
另一个相似变种 Dijkstra+DFS
Bellman-Ford算法和SPFA算法
\qquad Dijkstra算法可以很好的解决无负权值的图的最短路径问题，但如果出现了负权值，Dijkstra算法就会失效。为了解决这一问题，需要使用Bellman-Ford算法（简称BF算法）。该算法不仅可以处理单源最短路径问题，而且对于权值的正负没有要求。该算法只有一个要求，即没有从源点可达的负权值回路（回路的权值和为负）。
Floyd算法
\qquad 这个算法可以用来解决全源最短路径问题。即对给定图G(V,E),求任意两点u,v之间的最短路径的长度，时间复杂度是 O ( n 3 ) O(n^3) O(n3).Floyd算法基于这样一个事实：如果存在顶点k,使得以k为中介点时顶点i和顶点j的当前最短距离缩短，则使用顶点k作为顶点i和顶点j的中介点。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXV = 200;
const int INF = 1000000;
int n, m;
int dis[MAXV][MAXV]; //dis数组表示最短距离，dis[i][j]表示顶点i和顶点j的最短距离。
void Floyd() {
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (dis[i][k] != INF && dis[k][j] != INF && dis[i][k] + dis[k][j] < dis[i][j]) {
dis[i][j] = dis[i][k] + dis[k][j];
}
}
}
}
}
int main() {
int u, v, w;
fill(dis[0], dis[0] + MAXV * MAXV, INF); //dis数组赋初值。
cin >> n >> m; //顶点数和边数
for (int i = 0; i < n; ++i) {
dis[i][i] = 0;
}
for (int i = 0; i < m; ++i) {
cin >> u >> v >> w; //顶点和边权值
dis[u][v] = dis[v][u] = w;
}
Floyd();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << dis[i][j]<<" ";
}
cout << endl;
}
return 0;
}
这是图的最短路径问题的全部内容了。