邻接矩阵存储图,C++实现迪杰斯特拉
时间: 2024-05-18 15:12:07 浏览: 17
以下是使用 C++ 实现迪杰斯特拉算法的示例代码,假设图是使用邻接矩阵存储:
```cpp
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
#define V 6
int minDistance(int dist[], bool visited[]) {
int minDist = INT_MAX, minIndex;
for (int i = 0; i < V; i++) {
if (!visited[i] && dist[i] <= minDist) {
minDist = dist[i];
minIndex = i;
}
}
return minIndex;
}
void dijkstra(int graph[V][V], int start) {
int dist[V];
bool visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = false;
}
dist[start] = 0;
for (int i = 0; i < V - 1; i++) {
int u = minDistance(dist, visited);
visited[u] = true;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
cout << "Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++) {
cout << i << " \t\t " << dist[i] << endl;
}
}
int main() {
int graph[V][V] = {
{0, 4, 0, 0, 0, 0},
{4, 0, 8, 0, 0, 0},
{0, 8, 0, 7, 0, 4},
{0, 0, 7, 0, 9, 14},
{0, 0, 0, 9, 0, 10},
{0, 0, 4, 14, 10, 0}
};
dijkstra(graph, 0);
return 0;
}
```
该算法接受一个邻接矩阵,其中 graph[i][j] 表示从节点 i 到节点 j 的边的权重。 start 参数指定起点。该算法使用一个数组来存储每个节点的最短距离,以及一个布尔数组来存储每个节点是否已被访问。该算法使用一个循环来遍历每个节点,并在每次遍历中选择距离起点最近的未访问节点。对于每个未访问节点,该算法更新其最短距离,并标记为已访问。最后,该算法输出每个节点到起点的最短距离。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)