狄杰斯特拉算法c++怎么写
时间: 2024-05-12 19:19:17 浏览: 59
以下是基于C语言的Dijkstra算法实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
int graph[MAX_VERTICES][MAX_VERTICES]; // 定义图
int dist[MAX_VERTICES]; // 定义距离
int visited[MAX_VERTICES]; // 定义是否访问过
int min_distance(int dist[], int n) {
int min = INT_MAX, min_index;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] <= min) {
min = dist[i];
min_index = i;
}
}
return min_index;
}
void dijkstra(int src, int n) {
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
int u = min_distance(dist, n);
visited[u] = 1;
for (int v = 0; v < n; 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];
}
}
}
}
void add_edge(int u, int v, int w) {
graph[u][v] = w;
graph[v][u] = w;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add_edge(u, v, w);
}
dijkstra(0, n);
for (int i = 0; i < n; i++) {
printf("%d ", dist[i]);
}
printf("\n");
return 0;
}
```
使用方法如下:
输入格式为:`n m u1 v1 w1 u2 v2 w2 ... um vm wm`,其中n表示节点数,m表示边数,ui, vi表示边的两个节点,wi表示边的权值。
示例:输入 `5 7 0 1 2 0 2 6 1 2 3 1 3 8 1 4 5 2 4 7 3 4 2`,输出为 `0 2 5 8 7`。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)