狄杰斯特拉
时间: 2024-02-09 10:09:43 浏览: 139
狄杰斯特拉(Dijkstra)算法,也叫单源最短路径算法,是用于计算一个节点到其他所有节点的最短路径的算法。该算法常用于路由算法或作为其他图算法的一个子模块。
以下是狄杰斯特拉算法的基本思路:
1. 将所有节点分成两个集合:已知最短路径的节点集合和未知最短路径的节点集合。初始时,已知最短路径的节点集合只有起点,其他节点都在未知最短路径的节点集合中。
2. 对于所有的未知最短路径的节点,计算其到起点的距离,选择距离最小的节点加入已知最短路径的节点集合中。
3. 对于新加入已知最短路径的节点,更新其他未知最短路径的节点到起点的距离。
4. 重复步骤2和步骤3,直到所有节点都加入到已知最短路径的节点集合中。
以下是使用C++实现狄杰斯特拉算法的示例代码:
```c++
#include <iostream>
#include <climits>
using namespace std;
#define V 6 // 图的顶点数
#define INF INT_MAX // 定义无穷大
// 查找未知最短路径中距离起点最近的节点
int minDistance(int dist[], bool sptSet[]) {
int minDist = INT_MAX, minIndex;
for(int i = 0; i < V; i++) {
if(!sptSet[i] && dist[i] <= minDist) {
minDist = dist[i];
minIndex = i;
}
}
return minIndex;
}
// 执行狄杰斯特拉算法的函数
void dijkstra(int graph[V][V], int start) {
int dist[V]; // 存储节点到起点的距离
bool sptSet[V]; // 存储节点是否已知最短路径
// 初始化dist数组和sptSet数组
for(int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[start] = 0; // 起点到起点的距离为0
for(int i = 0; i < V - 1; i++) {
int u = minDistance(dist, sptSet); // 找到未知最短路径中距离起点最近的节点
sptSet[u] = true; // 将该节点加入已知最短路径的节点集合中
// 更新其他未知最短路径的节点到起点的距离
for(int v = 0; v < V; v++) {
if(!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 输出最短路径
cout << "节点\t\t到起点的距离" << endl;
for(int i = 0; i < V; i++) {
cout << i << "\t\t" << dist[i] << endl;
}
}
int main() {
int graph[V][V] = {
{0, 2, 4, 0, 0, 0},
{2, 0, 1, 4, 2, 0},
{4, 1, 0, 0, 3, 0},
{0, 4, 0, 0, 3, 2},
{0, 2, 3, 3, 0, 2},
{0, 0, 0, 2, 2, 0}
};
dijkstra(graph, 0); // 以0节点为起点执行狄杰斯特拉算法
return 0;
}
```
这个示例代码中的图是一个无向图,其邻接矩阵存储在graph数组中。运行程序后,将输出每个节点到起点的最短距离。