能否用邻接矩阵来存图呢
时间: 2023-10-20 20:49:20 浏览: 34
当然可以!以下是使用邻接矩阵来存储图,并使用Dijkstra算法求解最短路径的C++程序示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
// Dijkstra算法
void dijkstra(int start, int n, vector<vector<int>>& graph, vector<int>& dist) {
vector<bool> visited(n, false); // 记录顶点是否已经访问过
dist[start] = 0; // 起点的最短距离为0
for (int i = 0; i < n; ++i) {
int minDist = INF, u = -1;
for (int j = 0; j < n; ++j) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) {
break; // 所有顶点都已访问过,退出循环
}
visited[u] = true;
for (int v = 0; v < n; ++v) {
if (!visited[v] && graph[u][v] != INF && dist[v] > dist[u] + graph[u][v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
int n, m, start;
cout << "请输入顶点数、边数和起点编号:";
cin >> n >> m >> start;
vector<vector<int>> graph(n, vector<int>(n, INF)); // 邻接矩阵表示的图
vector<int> dist(n, INF);
cout << "请输入每条边的起点、终点和权值:" << endl;
for (int i = 0; i < m; ++i) {
int from, to, cost;
cin >> from >> to >> cost;
graph[from][to] = cost;
}
dijkstra(start, n, graph, dist);
cout << "从起点" << start << "到各个顶点的最短距离为:" << endl;
for (int i = 0; i < n; ++i) {
cout << "顶点" << i << ": ";
if (dist[i] == INF) {
cout << "INF" << endl;
} else {
cout << dist[i] << endl;
}
}
return 0;
}
```
你可以根据自己的需要修改顶点数、边数以及每条边的起点、终点和权值来测试程序。希望对你有帮助!
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)