实现Dijkstra算法,解决如下无向连通有权图的单源最短路径问题,源点为0点,在控制台窗口输出每个点到0点的最短距离和对应的路径。,图为A[9][9]={ 0,4,0,0,0,0,0,8,0, 4,0,8,0,0,0,0,11,0, 0,8,0,7,0,0,0,0,2, 0,0,0,0,9,14,0,0,0, 0,0,0,9,0,10,0,0,0, 0,0,4,14,10,0,0,0,0, 0,0,0,0,0,2,0,1,6, 8,11,0,0,0,0,1,0,7, 0,0,2,0,0,0,6,7,0 },要求用c++表示
时间: 2024-03-17 08:42:16 浏览: 114
下面是用C++实现Dijkstra算法的代码:
```cpp
#include <iostream>
#include <limits.h>
using namespace std;
#define V 9 // 定义顶点数
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
void printSolution(int dist[]) {
cout << "顶点到0点的最短距离为:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ":" << dist[i] << endl;
}
}
void dijkstra(int graph[V][V], int src) {
int dist[V]; // 存储最短距离
bool sptSet[V]; // 存储已经找到最短路径的顶点
// 初始化所有距离为无穷大,所有顶点都未处理过
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[src] = 0; // 起点到起点的距离为0
for (int count = 0; count < V - 1; count++) {
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];
}
}
}
printSolution(dist);
}
int main() {
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 0, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 0, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
```
输出结果为:
```
顶点到0点的最短距离为:
0:0
1:4
2:12
3:19
4:21
5:11
6:9
7:8
8:14
```
阅读全文