单源点路径问题使用迪杰特斯拉算法,c++代码实现
时间: 2023-12-26 14:03:35 浏览: 38
以下是使用迪杰特斯拉算法求单源点路径的C++代码实现,其中使用了邻接矩阵表示图:
```c++
#include <iostream>
#include <limits.h>
using namespace std;
#define V 5 // 图的顶点数
// 找到未被处理的最小距离顶点
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 printPath(int parent[], int j)
{
if (parent[j] == -1)
return;
printPath(parent, parent[j]);
cout << j << " ";
}
// 打印从源点到各顶点的最短路径
void printSolution(int dist[], int n, int parent[])
{
int src = 0;
cout << "顶点\t距离\t路径" << endl;
for (int i = 1; i < V; i++)
{
cout << src << "->" << i << "\t" << dist[i] << "\t" << src << " ";
printPath(parent, i);
cout << endl;
}
}
// 使用迪杰特斯拉算法求单源点路径
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // 存储从源点到各顶点的距离
bool sptSet[V]; // 已处理顶点的标记
int parent[V]; // 存储从源点到各顶点的路径
// 初始化
for (int i = 0; i < V; i++)
{
parent[0] = -1;
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[src] = 0;
// 处理V-1个顶点
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])
{
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
// 打印结果
printSolution(dist, V, parent);
}
int main()
{
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
dijkstra(graph, 0);
return 0;
}
```
上述代码中,我们首先定义了一个`V`宏表示图的顶点数。`minDistance()`函数用于找到未被处理的最小距离顶点,`printPath()`函数用于打印从源点到目标点的路径,`printSolution()`函数用于打印从源点到各顶点的最短路径。
在`dijkstra()`函数中,我们初始化了`dist`数组(存储从源点到各顶点的距离)、`sptSet`数组(已处理顶点的标记)和`parent`数组(存储从源点到各顶点的路径)。然后,我们选出未被处理的最小距离顶点,并更新其它顶点的距离。最后,我们打印出从源点到各顶点的最短路径。
在`main()`函数中,我们定义了一个邻接矩阵`graph`表示图,并调用`dijkstra()`函数求解单源点路径问题。
相关推荐
![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_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)