dijstra算法c++
时间: 2023-08-16 10:13:12 浏览: 44
Dijkstra算法是一种用于解决单源最短路径问题的经典算法。下面是一个简单的C++实现示例:
```cpp
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
// Dijkstra算法函数
void Dijkstra(vector<vector<int>>& graph, int start) {
int n = graph.size();
vector<int> distance(n, INF); // 存储起始点到每个顶点的最短距离
vector<bool> visited(n, false); // 记录顶点是否被访问过
distance[start] = 0; // 起始点到自身的距离为0
// 找到距离起始点最近的顶点
for (int i = 0; i < n - 1; i++) {
int minDist = INF;
int minIndex = -1;
// 从尚未访问的顶点中找到距离起始点最近的顶点
for (int j = 0; j < n; j++) {
if (!visited[j] && distance[j] < minDist) {
minDist = distance[j];
minIndex = j;
}
}
if (minIndex == -1) {
break; // 若没有找到最近的顶点,则退出循环
}
visited[minIndex] = true; // 标记该顶点为已访问
// 更新与最近顶点相邻顶点的距离
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[minIndex][j] != INF && distance[minIndex] + graph[minIndex][j] < distance[j]) {
distance[j] = distance[minIndex] + graph[minIndex][j];
}
}
}
// 输出最短距离
cout << "Vertex\tDistance" << endl;
for (int i = 0; i < n; i++) {
cout << i << "\t" << distance[i] << endl;
}
}
int main() {
// 构建图的邻接矩阵
vector<vector<int>> graph = {
{0, 4, INF, INF, INF, INF, INF, 8, INF},
{4, 0, 8, INF, INF, INF, INF, 11, INF},
{INF, 8, 0, 7, INF, 4, INF, INF, 2},
{INF, INF, 7, 0, 9, 14, INF, INF, INF},
{INF, INF, INF, 9, 0, 10, INF, INF, INF},
{INF, INF, 4, 14, 10, 0, 2, INF, INF},
{INF, INF, INF, INF, INF, 2, 0, 1, 6},
{8, 11, INF, INF, INF, INF, 1, 0, 7},
{INF, INF, 2, INF, INF, INF, 6, 7, 0}
};
int start = 0; // 起始点
Dijkstra(graph, start);
return 0;
}
```
这段代码使用邻接矩阵表示图,其中`INF`表示不可达的边。在`main`函数中,我们构建了一个图,并指定了起始点为0。然后调用`Dijkstra`函数计算起始点到每个顶点的最短距离,并将结果输出到控制台。请注意,该示例仅适用于有向图。如需适用于无向图,只需将邻接矩阵对称即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)