最短路径问题是图论中比较重要的一类问题，这类问题旨在寻找图中两结点之间的最短路径。最短路径算法包括以下几种形式：
迪杰斯特拉算法 \textit{迪杰斯特拉算法} 迪杰斯特拉算法（
Dijkstra's algorithm），Dijkstra算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的 单源最短路径 问题，单源最短路 指的是求一个源点到其他顶点（结点）的最短路径。注意该算法 无法解决权值是负值 情况的最短路问题。
该算法解决了图 G = ⟨ V , E ⟩ {\displaystyle G=\langle V,E\rangle } G=⟨V,E⟩ 上带权的单源最短路径问题。
d [ v ] {\displaystyle d[v]} d[v] 表示的是源点 s {\displaystyle s} s 到顶点 v {\displaystyle v} v 的距离。 w ( u , v ) w(u,v) w(u,v) 表示的是 u − v {\displaystyle u-v} u−v 边的权值
松弛 是该算法中的核心内容，指的是如果存在一条从顶点 u {\displaystyle u} u 到顶点 v {\displaystyle v} v 的边，那么从 s {\displaystyle s} s 到 v {\displaystyle v} v 的一条新路径是将边 u − v {\displaystyle u-v} u−v 添加到从 s {\displaystyle s} s 到 u {\displaystyle u} u 的路径尾部来拓展一条从 s {\displaystyle s} s 到 v {\displaystyle v} v 的路径。这条路径的长度是 d [ v ] = d [ u ] + w ( u , v ) {\displaystyle d[v] = d[u]+w(u,v)} d[v]=d[u]+w(u,v) 。如果这个值比目前已知的 d [ v ] {\displaystyle d[v]} d[v] 的值要小，那么可以用这个值来替代当前 d [ v ] {\displaystyle d[v]} d[v] 的值。松弛边的操作一直执行到所有的 d [ v ] {\displaystyle d[v]} d[v] 都表示为从顶点 s {\displaystyle s} s 到顶点 v {\displaystyle v} v 的最短路径的长度值。
作者对顶点设计了两个集合 S {\displaystyle S} S 和 U {\displaystyle U} U , S {\displaystyle S} S 中存放的是所有与源点 s {\displaystyle s} s 之间的距离最短的顶点， U {\displaystyle U} U 中存放的是目前其他剩余的顶点。集合 S {\displaystyle S} S 初始状态为空，而后每一步都有一个顶点从 U {\displaystyle U} U 移动到 S {\displaystyle S} S 。这个被选择的顶点是 U {\displaystyle U} U 中拥有最小的 d [ u ] {\displaystyle d[u]} d[u] 值的顶点。当一个顶点 u {\displaystyle u} u 从 U {\displaystyle U} U 中转移到了 S {\displaystyle S} S 中，算法对 u {\displaystyle u} u 的每条外接边 w ( u , v ) {\displaystyle w(u,v)} w(u,v) 进行松弛。
现在利用下图来说明 Dijkstra 算法，这是表示城市之间所有路径之间权重的一幅图。图中的圈圈表示的是 城市， 城市与城市之间的连线表示当前两城市之间有一条 连通路径，数值 表示路径距离，这些分别对应图论中的 顶点、边 和 权值。
这里选取城市
0作为出发点。当然也可以选取其他城市作为出发点。
维护两个集合S和U, 分别用来存放当前与源点已经是最短路径的顶点和其他的顶点。
维护一个数组dist[u]表示u与源点src的距离。
| 集合 S S S | 集合 U U U |
|---|---|
| S = ϕ S = \phi S=ϕ | U = { 0 , 1 , 2 , 3 } U = {\{0, 1, 2, 3\}} U={0,1,2,3}，默认 d i s t [ i ] = ∞ , i ∈ U dist[i] = \infin, i\in U dist[i]=∞,i∈U ； |
| 选入
0
0
0, 此时
S
=
{
0
}
S = \{0\}
S={0}, 更新 d i s t [ 0 ] = 0 dist[0] = 0 dist[0]=0 ； |
U
=
{
1
,
2
,
3
}
U = {\{1, 2, 3\}}
U={1,2,3}, d i s t [ 1 ] = 3 dist[1] = 3 dist[1]=3, d i s t [ 2 ] = ∞ dist[2] = \infin dist[2]=∞, d i s t [ 3 ] = ∞ dist[3] = \infin dist[3]=∞ ; |
| 选入
1
1
1,此时
S
=
{
0
,
1
}
S = \{0, 1\}
S={0,1}, 开始进行松弛操作； |
U
=
{
2
,
3
}
U = {\{2, 3\}}
U={2,3}, d i s t [ 2 ] = 4 < ∞ dist[2] = 4 < \infin dist[2]=4<∞, d i s t [ 3 ] = 7 < ∞ dist[3] = 7 < \infin dist[3]=7<∞ ; |
| 选入
2
2
2,此时
S
=
{
0
,
1
,
2
}
S = \{0, 1, 2\}
S={0,1,2}, 继续进行松弛操作； |
U
=
{
3
}
U = {\{3\}}
U={3}, d i s t [ 3 ] = 5 < 7 dist[3] = 5 < 7 dist[3]=5<7 ; |
| 选入
3
3
3,此时
S
=
{
0
,
1
,
2
，
3
}
S = \{0, 1, 2，3\}
S={0,1,2，3}， 最短路径已经出炉了！ \color{red}{最短路径已经出炉了！} 最短路径已经出炉了！ d i s t [ 0 ] = 0 \color{red}{dist[0] = 0} dist[0]=0 d i s t [ 1 ] = 3 \color{red}{dist[1] = 3} dist[1]=3 d i s t [ 2 ] = 4 \color{red}{dist[2] = 4} dist[2]=4 d i s t [ 3 ] = 5 \color{red}{dist[3] = 5} dist[3]=5 |
U = ϕ U = \phi U=ϕ ; |
#include <iostream>
using namespace std;
#define maxn 110
#define INF 0x3f3f3f3f
// 根据边权图建边（邻接矩阵）
int edges[maxn][maxn]; // 邻接矩阵
int dist[maxn]; // 距离源点的数组
bool visited[maxn]; // 是否已经找到最短路
void init(int n) {
int i, j;
memset(edges, INF, sizeof(edges)); // 初始化邻接矩阵
memset(visited, false, sizeof(visited));
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
if (i == j) {
edges[i][j] = 0;
}
}
}
}
void dijkstra(int src, int n){
int i, j, p;
// 初始化 dist[]
for (i = 0; i < n; ++i) {
dist[i] = edges[src][i];
}
visited[src] = true;
while (true) {
p = -1;
int mn = INF;
for (i = 0; i < n; ++i) {
// 在dist[]找一个最小的路径，并将这条路到达的顶点记录
// 通过遍历 S 集合的方法，寻找最小路径的顶点，此处可以通过优先队列的方法优化
if (!visited[i] && dist[i] < mn) {
mn = dist[i];
p = i;
}
}
visited[p] = true;
if (p == -1) {
break;
}
for (i = 0; i < n; ++i) {
if (!visited[i] && mn + edges[p][i] < dist[i]) {
dist[i] = mn + edges[p][i];
}
}
}
}
int main()
{
cout << "现在开始建立邻接矩阵：" << endl;
int n, m;
int i, j;
cout << "请输入顶点数量和边的数量：" << endl;
cin >> n >> m;
init(n);
cout << "请输入边的起点、终点以及距离：" << endl;
for (i = 0; i < m; ++i) {
int u, v, wt;
cin >> u >> v >> wt;
edges[u][v] = edges[v][u] = wt;
}
cout << "请输入起点城市：" << endl;
int start;
cin >> start;
dijkstra(start, n);
cout << "起点城市到所有城市的最小距离为：" << endl;
for (j = 0; j < n; ++j) {
cout << start << "->" << j << "最小路径为" << dist[j] << endl;
}
return 0;
}
最终的结果如图所示：
以上图为例子，实现 Dijkstra+Heap 方法。
通过设置
s
h
o
r
t
e
s
t
P
a
t
h
(
a
d
j
,
V
,
0
)
shortestPath(adj, V, 0)
shortestPath(adj,V,0)函数的参数，可以实现计算任意点到源点的距离。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
// iPair ==> Integer Pair（整数对）
typedef pair<int, int> iPair;
// 加边
void addEdge(vector<pair<int, int>> adj[], int u, int v, int wt){
// u-v 边的权值是 wt
// v-u 边的权值是 wt，因为这里是无向图
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// 计算最短路
void shortestPath(vector<pair<int, int>> adj[], int V, int src){
priority_queue<iPair, vector <iPair>, greater<iPair> > pq;
// 距离置为正无穷大
vector<int> dist(V, INF);
vector<bool> visited(V, false);
// 插入源点，距离为0
pq.push(make_pair(0, src)); // 这里的整数对表示 距离，顶点
dist[src] = 0;
/* 循环直到优先队列为空 */
while (!pq.empty()){
// 每次从优先队列中取出顶点事实上是这一轮最短路径权值确定的点
int u = pq.top().second;
pq.pop();
if (!visited[u]) {
continue;
}
visited[u] = true;
// 遍历所有边
for (auto x : adj[u]){
// 得到顶点边号以及边权
int v = x.first;
int weight = x.second;
//可以松弛
if (dist[v] > dist[u] + weight){
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
// 打印最短路
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; ++i) {
printf("%d \t %d\n", i, dist[i]);
}
}
int main(){
const int V = 5;
vector<iPair> adj[V];
addEdge(adj, 0, 1, 2);
addEdge(adj, 0, 4, 8);
addEdge(adj, 1, 2, 3);
addEdge(adj, 1, 4, 2);
addEdge(adj, 2, 3, 1);
addEdge(adj, 3, 4, 1);
shortestPath(adj, V, 0);
return 0;
}
输出结果为：
Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法[1]，是解决任意两点间的最短路径的一种算法[2]，可以正确处理有向图或 负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包[3]。
弗洛伊德算法可以解决任意两点之间的最短路径问题，即多源最短路问题。通过不断选择顶点 k 作为两个顶点间的中转顶点来更新这两个顶点之间的距离的方法，达到求解任意两个顶点之间最短路径距离的目的。
该算法定义了两个二维矩阵：
在上图所示的第1步中，首先初始化表示任意两个顶点之间最短距离的矩阵Dist，无法直达的两个顶点之间的最短距离初始化为 INF，表示无穷大值。
在第2步中，以顶点A为中转点。原矩阵中，Dist[B][C] = INF，经过中转点的沟通，有Dist[B][A] + Dist[A][C] = 26 < INF，因此更新Dist[B][C] = 26，对应的 Dist[C][B] = 26
在第3步中，以顶点B为中转点。有Dist[A][B] +Dist[B][E] = 22 < Dist[A][E] = INF，因此更新Dist[A][E] = 22，对应的 Dist[E][A] = 22；类似的有 Dist[C][E] = Dist[E][C] = 36。
如此推导下去，直至遍历完所有可能的中转点，更新矩阵得到最终结果。
// 弗洛伊德算法核心伪代码
for (k = 0; k < vertexNum; ++k) { // 中转点
for (v = 0; v < vertexNum; ++v) { // 起点
for (w = 0; w <vertexNum; ++w) { // 终点
if (D[v][w] > D[v][k] + D[k][w]) {
D[v][w] = D[v][k] + D[k][w]; // 更新最小路径值
P[v][w] = P[v][k]; // 更新中转点
}
}
}
}
完整C++代码实现
#include <iostream>
#include <vector>
using namespace std;
int n; //全局变量
void short_path_floyd(vector<int, vector<int>>& graphy, vector<int, vector<int>>& D, vector<int, vector<int>>& P) {
int v, w, k;
// 初始化 D，P矩阵
for (v = 0; v < n; ++v) {
for (w = 0; w < n; ++w) {
D[v][w] = graphy[v][w];
P[v][w] = w;
}
}
// 核心代码
for (k = 0; k < n; ++k) {
for (v = 0; v < n; ++v) {
for (w = 0; w < n; ++w) {
if (D[v][w] > D[v][k] + D[k][w]) {
D[v][w] = D[v][k] + D[k][w];
P[v][w] = P[v][k];
}
}
}
}
// 输出更新后的 D 矩阵
cout << "输出更新后的矩阵 D:"
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << D[i][j];
}
cout << endl;
}
// 输出更新后的 P 矩阵
cout << "输出更新后的矩阵 D:"
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << P[i][j];
}
cout << endl;
}
}
int main() {
// 01 先建立图
cout << "请输入顶点数" << endl;
vector<int, vector<int>> graphy(n, vector<int>(n, INT_MAX));
cin >> n;
int i, j;
// 键盘输入 初始化矩阵值
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
cin >> graphy[i][j];
}
}
cout << "键盘输入的矩阵值：" << endl;
for (i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
cout << graphy[i][j];
}
cout << endl;
}
// 02 建立 P 和 D 矩阵
vector<int, vector<int>> vertexK(n, vector<int>(n));
vector<int, vector<int>> minDist(n, vector<int>(n, INT_MAX));
// 03 弗洛伊德法求最短路径
short_path_floyd(graphy, vertexK, minDist);
// 04 验证
// 求 0-3 的最小路径
int v, w, k;
v = 0;
w = 3;
cout << v << "到" << w << "的最小路径值为:" << minDist[v][w];
int k = vertexK[v][w];
cout << "path:" << v;
while (k != w) {
cout << " -> " << k;
k = vertexK[k][w];
}
return 0;
}
贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行 ∣ V ∣ − 1 {\displaystyle |V|-1} ∣V∣−1 次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O ( ∣ V ∣ ∣ E ∣ ) {\displaystyle O(|V||E|)} O(∣V∣∣E∣) 。但算法可以进行若干种优化，提高了效率。
贝尔曼-福特算法是一种在图中求解单源最短路径问题的算法。单源最短路也就是求一个源点到图中其他顶点的最短路径。如同 Dijkstra 算法一样核心都是 松弛 操作。对于一个有n个顶点的图，最坏情况下进行 n-1 轮对每条边的松弛操作，就可以得到最短路径。 贝尔曼-福特算法比起 Dijkstra 算法来说，可以解决带有负值的边权以及存在负环的情况，而 Dijkstra 算法不能处理以上两种情况。
首先通过一个如下图所示的有向图来说明带有负值边权的图的单源最短路问题。以A点为源点，计算其他顶点到源点的最小距离。初始化距离，源点A到自身的距离为0，其他点的初始化距离为无穷大，用 INF 表示。
第一轮松弛操作开始，遍历所有的边：
① 遍历AB边，Edges[A][B] = 5 < INF = dist[A][B]，因此更新dist[A][B] = 5；
② 遍历AC边，Edges[A][C] = -2 < INF = dist[A][C]，因此更新dist[A][C] = -2；
③ 遍历BE边，dist[A][B] + Edges[B][E] = 6 < INF = dist[A][E]，因此更新dist[A][E] = 6；
④ 遍历CB边，dist[A][C] + Edges[C][B] = 0 < 5 = dist[A][B]，因此更新 dist[A][B] = 0；
⑤ 遍历CF边，dist[A][C] + Edges[C][F] = 1 < INF = dist[A][F]，因此更新 dist[A][F] = 1；
⑥ 遍历EC边，dist[A][E] + Edges[E][C] = 8 > -2 = dist[AC]，因此 不需要 更新 dist[A][C]；
⑦ 遍历ED边，dist[A][E] + Edges[E][D] = 9 < INF = dist[A][D]，因此更新 dist[A][D] = 9；
⑧ 遍历EF边，dist[A][E] + Edges[E][F] = 16 > 1 = dist[A][F]，因此 不需要 更新 dist[A][D]；
⑨ 遍历FD边，dist[A][F] + Edges[F][D] = 11 > 9 = dist[A][D]，因此 不需要 更新 dist[A][D];
至此第一轮松弛操作全部结束。
第二轮松弛操作开始，遍历所有的边：
① 遍历AB边，不需要更新；
② 遍历AC边，不需要更新；
③ 遍历BE边，dist[A][B] + Edges[B][E] = 1 < 6 = dist[A][E]，因此更新 dist[A][E] = 1；
④ 遍历CB边，不需要更新；
⑤ 遍历CF边，不需要更新；
⑥ 遍历EC边，不需要更新；
⑦ 遍历ED边，dist[A][E] + Edges[E][D] = 4 < 9 = dist[A][D]，因此更新 dist[A][D] = 4；
⑧ 遍历EF边，不需要更新；
⑨ 遍历FD边，不需要更新；
进行第三轮松弛操作的时候最短路径值已经不更新了，后面第 4、5 轮（顶点数-1）轮松弛操作已经不需要了，因为已经得出最终答案了。
在这里只需要通过两轮对所有边的松弛操作就得到了最短路径，那么后续的几轮松弛操作不就冗余了吗。那会不会有其他更优的方法来解决这类问题了，想到这里说明大家已经基本掌握了贝尔曼-福特算法了，已经能够有更加深入的思考了。关于如何继续优化将在下一个最短路径算法中讲解。
因为负权环可以无限制的降低总花费，所以如果发现第 n n n 次操作仍可降低花销，就一定存在负权环，这里的 n n n 指的就是图中顶点的个数。当出现负权环的时候，表明此图无法进行单源最短路问题求解。
// 贝尔曼-福特核心伪代码
procedure BellmanFord(list vertices, list edges, vertex source)
// 读入边和节点的列表并对distance和predecessor写入最短路径
// 初始化图
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// 对每一条边重复操作
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// 检查是否有负权重的回路
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "图包含负权重的回路"
#include <iostream>
#include <vector>
using namespace std;
const int N = 100, M = 100; // 顶点和边最大数量
int n, m; // 输入的顶点和边数
int dist[N]; // 记录最短距离数组
int pred[N]; // 记录前驱顶点
struct Edge{
int a, b, wt; // 分别表示边的起点、终点和权值
} edges[M];
void BellmanFord() {
// 初始化距离数组
memset(dist, 0x3f, sizeof(dist));
memset(pred, 0, sizeof(pred));
dist[0] = 0; // 0 是源点表示的是顶点 A
// n-1 次松弛操作
for (int i = 0; i < n-1; ++i) {
// 遍历图中所有的边
for (int j = 0; j < m; ++j) {
int a = edges[j].a;
int b = edges[j].b;
int wt = edges[j].wt;
if (dist[b] > dist[a] + wt) {
dist[b] = dist[a] + wt
pred[b] = a;
}
}
}
// 第 n 次松弛操作，即检查图中是否有负权图
for (int j = 0; j < m; ++j) {
int a = edges[j].a;
int b = edges[j].b;
int wt = edges[j].wt;
if (dist[b] > dist[a] + wt) {
cout << "图包含负权重的回路" << endl;
break;
}
}
}
int main() {
// 输入顶点数和边数
cin >> n >> m;
// 读入边
for (int i = 0; i < m; ++i) {
int a, b, wt;
cin >> a >> b >> wt;
edges[i] = {a, b, wt};
}
// 调用 BellanFord() 算法
BellmanFord();
// 输出 dist 数组
for (int i = 0; i < n; ++i) {
cout << dist[i] << " ";
}
cout << endl;
// 输入指定终点查询最短距离及路径
cout << "输入指定终点查询最短距离及路径，终点范围为（0-n-1）" << endl;
int endVer;
cin >> endVer;
cout << "shortest Distance from A is " << dist[endVer] << end;
cout << "short path: A -> ";
int ver = endVer;
while (ver != 0) {
cout << pred[ver] << "->";
ver = pred[ver];
}
return 0;
}
SPFA算法是贝尔曼-福特算法的改进版本。
SPFA算法核心思想依然是松弛操作，只是不需要松弛 N-1 次了，经过对贝尔曼-福特算法的研究发现，没有必要松弛 N-1 轮，并且不需要对每一条边进行松弛。SPFA 一个优化操作就是利用队列来维护哪些顶点可能会需要松弛操作，这样一来只需要访问一些必要的边了。
维护一个队列存放顶点，维护一个数组用来判断顶点是否访问过。
首先将源点入队，如果队列不为空，然后重复执行以下步骤：
判断负权环的情况，当某个顶点进入队列的次数超过 N(顶点数) 时则判断存在负权环。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 100, M = 100; // 顶点和边最大数量
int n, m, s; // 输入的顶点和边数和源点
int dist[N]; // 记录最短距离数组
int pred[N]; // 记录前驱顶点
int cnt[N];
bool vist[N];
struct Edge{
int a, b, wt; // 分别表示边的起点、终点和权值
} edges[M];
void SPFA(int s) {
// 初始化距离数组
memset(dist, 0x3f, sizeof(dist));
memset(pred, 0, sizeof(pred));
memset(vist, false, sizeof(vist));
memset(cnt, 0, sizeof(cnt));
dist[0] = 0; // 0 是源点表示的是顶点 A
queue<int> que;
que.push(s);
while (!que.empty()) {
int q = que.front();
que.pop();
vist[q] = true;
for (int j = 0; j < m; ++j) {
int a = edges[j].a;
if (a == t) {
int b = edges.b;
int wt = edges.wt;
if (dist[b] > dist[a] + wt) {
dist[b] = dist[a] + wt;
cnt[b] = cnt[a] + 1;
if (cnt[b] >= n) {
cout << "图中包含负权重的回路!" << endl;
break;
}
if (!vist[b]) {
vist[b] = true;
que.push(b);
}
}
}
}
cout << "图中不包含负权重的回路!" << endl;
}
}
int main() {
// 输入顶点数和边数和源点
cin >> n >> m >> s;
// 读入边
for (int i = 0; i < m; ++i) {
int a, b, wt;
cin >> a >> b >> wt;
edges[i] = {a, b, wt};
}
// 调用 SPFA() 算法
SPFA(s);
// 输出 dist 数组
for (int i = 0; i < n; ++i) {
cout << dist[i] << " ";
}
cout << endl;
// 输入指定终点查询最短距离及路径
cout << "输入指定终点查询最短距离及路径，终点范围为（0-n-1）" << endl;
int endVer;
cin >> endVer;
cout << "shortest Distance from A is " << dist[endVer] << end;
cout << "short path: A -> ";
int ver = endVer;
while (ver != 0) {
cout << pred[ver] << "->";
ver = pred[ver];
}
return 0;
}
1、戴克斯特拉算法-维基百科
由于本篇博客参考内容众多，加上时间久远，一些参考文章已经找不到了，所以这里没有放出所有的参考链接，请见谅。
此篇博客是关于 最短路径问题 的第一次总结，难免会有一些疏漏甚至是错误之处，如有不足以及错误之处，欢迎指出大家一起交流学习。还有一篇关于启发式搜索的 A* 算法，敬请期待，持续更新中。