请用c语言编写Dijkstra算法,要求可测试任意加权图
时间: 2024-03-10 14:49:08 浏览: 21
好的,以下是使用C语言编写的Dijkstra算法的示例代码。该代码可以处理任意加权图,并且可以通过修改main函数中的输入数据进行测试。
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 100
#define MAX_EDGES 10000
typedef struct {
int u, v, weight;
} Edge;
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int n, int start, int dist[MAX_VERTICES], int prev[MAX_VERTICES]) {
int visited[MAX_VERTICES] = {0};
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
prev[i] = -1;
}
dist[start] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u]))
u = j;
}
if (dist[u] == INT_MAX)
break;
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0) {
int new_dist = dist[u] + graph[u][v];
if (new_dist < dist[v]) {
dist[v] = new_dist;
prev[v] = u;
}
}
}
}
}
void print_path(int prev[MAX_VERTICES], int start, int end) {
if (end == start)
printf("%d", start);
else if (prev[end] == -1)
printf("No path from %d to %d", start, end);
else {
print_path(prev, start, prev[end]);
printf(" -> %d", end);
}
}
int main() {
int n, m;
int graph[MAX_VERTICES][MAX_VERTICES] = {0};
Edge edges[MAX_EDGES];
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the number of edges: ");
scanf("%d", &m);
printf("Enter the edges in the format u v weight:\n");
for (int i = 0; i < m; i++)
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
for (int i = 0; i < m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int weight = edges[i].weight;
graph[u][v] = weight;
graph[v][u] = weight;
}
int start, end;
printf("Enter the start vertex: ");
scanf("%d", &start);
printf("Enter the end vertex: ");
scanf("%d", &end);
int dist[MAX_VERTICES];
int prev[MAX_VERTICES];
dijkstra(graph, n, start, dist, prev);
printf("Shortest path from %d to %d is: ", start, end);
print_path(prev, start, end);
printf("\n");
return 0;
}
```
注意:这段代码使用的是邻接矩阵来表示图,如果你使用的是邻接表或其他数据结构来表示图,需要相应地修改代码。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pages](https://img-home.csdnimg.cn/images/20210720083646.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_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)