C++简单实现Dijkstra算法
什么是Dijkstra算法
Dijkstra算法是一种贪心算法,用于解决带权图的单源最短路径问题。它的主要思想是从起点开始,找到距离它最近的节点,将该节点加入已访问的节点中,然后更新其他节点到起点的距离。重复以上步骤,直到找到终点或者所有的节点都被访问。
算法流程
步骤如下:
- 初始化:将起点的距离设为0,其他节点的距离设为无穷大。将所有节点加入集合S中。
- 找到S中距离起点最近的节点u,将其加入已访问的节点集合V中。
- 对于所有与节点u相邻的节点v,更新其到起点的距离,如果有更短的路径,更新其距离。
- 重复步骤2和步骤3,直到所有的节点都被访问过。
示例代码
#include <iostream>
#include <climits>
using namespace std;
const int MAXN = 100005;//可以根据题目要求修改
int d[MAXN];
bool used[MAXN];
int V, E;//V表示节点个数,E表示边的个数
struct edge {
int to;
int cost;
};
edge G[MAXN][MAXN];//邻接矩阵存图
void dijkstra(int s) {
// 初始化
for (int i = 1; i <= V; i++) {
d[i] = INT_MAX;//将除了起点之外的节点距离都设置为无穷大
used[i] = false;
}
d[s] = 0;
while (true) {
int v = -1;
for (int u = 1; u <= V; u++) {
if (!used[u] && (v == -1 || d[u] < d[v])) {
v = u;
}
}
if (v == -1) {
break;
}
used[v] = true;
// 更新所有与节点v相邻的节点的距离
for (int u = 1; u <= V; u++) {
if (G[v][u].cost != INT_MAX) {//如果u和v之间有边相连
d[u] = min(d[u], d[v] + G[v][u].cost);//判断是否需要更新距离
}
}
}
}
示例说明
例子1
给定起点S,终点T,求S到T的最短路径。
图中的数字表示边的权值。
(4)
S ------ T
/ \ / \
(2) (3) (2) (5)
/ \ / \
A B C
使用邻接矩阵存图的方式,在程序中输入该图的边的信息,然后使用Dijkstra算法求S到T的最短路径。
int main() {
V = 4;
E = 5;
// 初始化邻接矩阵
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
G[i][j].cost = INT_MAX;
}
}
G[1][2].cost = 2;
G[1][3].cost = 3;
G[2][3].cost = 2;
G[2][4].cost = 5;
G[3][4].cost = 4;
G[2][1].cost = 2;
G[3][1].cost = 3;
G[3][2].cost = 2;
G[4][2].cost = 5;
G[4][3].cost = 4;
// 求最短路径
dijkstra(1);
// 输出结果:输出所有节点到起点的最短路径
for (int i = 1; i <= V; i++) {
cout << "distance from S to " << i << ": " << d[i] << endl;
}
return 0;
}
输出结果:
distance from S to 1: 0
distance from S to 2: 2
distance from S to 3: 3
distance from S to 4: 7
例子2
实际应用经常涉及到多个起点或终点的情况,求出这些点到其他节点的最短路径。
例如,从下面的图中的点1、2和7,分别到其他节点的最短路径。
(2)
/ \
(4)/ \ (3)
/ \
1-------(6)--------2
\ /
(5)\ /(4)
\ /
(1)
7
多源最短路径问题可以把每个起点作为开始运行Dijkstra算法,最终获得每个点到起点的最短路径。这种方法叫做 Floyd 算法,时间复杂度较高,但对于较小的图来说是可行的。
// 计算多源最短路径
void floyd() {
for (int k = 1; k <= V; k++) {
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
G[i][j].cost = min(G[i][j].cost, G[i][k].cost + G[k][j].cost);
}
}
}
}
int main() {
V = 7;
E = 10;
// 初始化邻接矩阵
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
if (i == j) {
G[i][j].cost = 0;
} else {
G[i][j].cost = INT_MAX;
}
}
}
G[1][2].cost = 6;
G[1][7].cost = 1;
G[2][1].cost = 6;
G[2][3].cost = 5;
G[2][7].cost = 2;
G[3][2].cost = 5;
G[3][4].cost = 5;
G[4][3].cost = 5;
G[4][5].cost = 4;
G[5][4].cost = 4;
G[5][6].cost = 3;
G[6][5].cost = 3;
G[6][7].cost = 9;
G[7][1].cost = 1;
G[7][2].cost = 2;
G[7][6].cost = 9;
// 求多源最短路径
floyd();
// 输出结果:输出从点1、2、7到其他节点的最短路径
cout << "distance from 1 to:" << endl;
for (int i = 1; i <= V; i++) {
cout << i << ": " << G[1][i].cost << endl;
}
cout << "distance from 2 to:" << endl;
for (int i = 1; i <= V; i++) {
cout << i << ": " << G[2][i].cost << endl;
}
cout << "distance from 7 to:" << endl;
for (int i = 1; i <= V; i++) {
cout << i << ": " << G[7][i].cost << endl;
}
return 0;
}
输出结果:
distance from 1 to:
1: 0
2: 6
3: 11
4: 16
5: 20
6: 23
7: 1
distance from 2 to:
1: 6
2: 0
3: 5
4: 10
5: 14
6: 17
7: 2
distance from 7 to:
1: 1
2: 2
3: 7
4: 12
5: 16
6: 9
7: 0
总结
Dijkstra算法可以求单源最短路径问题,时间复杂度为O(N^2),当边很多时会很慢。若边很多(如>10^6,即100W),则可以使用堆优化版的Dijkstra算法,时间复杂度降为O(ElogV)。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++简单实现Dijkstra算法 - Python技术站