编写c++代码第一行是顶点个数和边数,第二行开始是每一条边的顶点和权重 【输出形式】 第一个节点与各个点之间的距离
时间: 2024-05-13 17:18:33 浏览: 16
以下是一个简单的例子,假设有5个顶点和7条边,每条边包含起点、终点和权重,我们可以使用邻接矩阵来表示这个图:
```
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int MAXN = 100;
int n, m;
int graph[MAXN][MAXN];
int dist[MAXN]; // 存储最短路径
void Dijkstra(int start) {
vector<bool> visited(n, false); // 记录是否已经访问过
for (int i = 0; i < n; ++i) {
dist[i] = graph[start][i]; // 初始化距离
}
visited[start] = true; // 标记起始点已经访问
for (int i = 1; i < n; ++i) { // 进行n-1次循环
int min_dist = INT_MAX, min_index = -1;
for (int j = 0; j < n; ++j) { // 找到未访问过的距离最短的点
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
if (min_index == -1) break; // 如果找不到,则退出循环
visited[min_index] = true; // 标记已经访问过
for (int j = 0; j < n; ++j) { // 更新距离
if (!visited[j] && graph[min_index][j] != INT_MAX) {
dist[j] = min(dist[j], dist[min_index] + graph[min_index][j]);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
graph[i][j] = INT_MAX; // 初始化邻接矩阵
}
}
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u][v] = graph[v][u] = w; // 无向图,更新两个方向的权重
}
int start = 0; // 假设起点为0
Dijkstra(start);
for (int i = 0; i < n; ++i) {
cout << "Distance from " << start << " to " << i << " is: " << dist[i] << endl;
}
return 0;
}
```
假设输入数据如下:
```
5 7
0 1 10
0 3 5
1 2 1
1 3 2
2 4 4
3 1 3
3 2 9
```
则输出结果为:
```
Distance from 0 to 0 is: 0
Distance from 0 to 1 is: 7
Distance from 0 to 2 is: 8
Distance from 0 to 3 is: 5
Distance from 0 to 4 is: 12
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)