用c语言设计最短路径算法,要求编程实现求任意两顶点之间的最短路径,注意是任意两顶点
时间: 2024-03-18 18:40:41 浏览: 23
好的,我可以为您提供一个基于Dijkstra算法的C语言实现,用于求解任意两个顶点之间的最短路径。下面是代码示例:
```c
#include <stdio.h>
#include <limits.h>
#define V 6 // 顶点数
#define INFINITY INT_MAX
int graph[V][V] = { // 图的邻接矩阵
{0, 2, 4, 1, INFINITY, INFINITY},
{2, 0, INFINITY, 3, 10, INFINITY},
{4, INFINITY, 0, 2, INFINITY, 5},
{1, 3, 2, 0, 7, 8},
{INFINITY, 10, INFINITY, 7, 0, INFINITY},
{INFINITY, INFINITY, 5, 8, INFINITY, 0}
};
void dijkstra(int start, int dist[]) {
int visited[V] = {0}; // 记录是否访问过
dist[start] = 0;
for (int i = 0; i < V; i++) {
int min_dist = INFINITY, u = -1;
for (int j = 0; j < V; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
u = j;
}
}
if (u == -1) break;
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (!visited[v] && graph[u][v] != INFINITY && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main() {
int dist[V];
int start = 0; // 起点
for (int i = 0; i < V; i++) {
dist[i] = INFINITY;
}
dijkstra(start, dist);
for (int i = 0; i < V; i++) {
printf("Distance from %d to %d is %d\n", start, i, dist[i]);
}
return 0;
}
```
在这个示例中,我们使用了邻接矩阵来表示图,并实现了Dijkstra算法来求解最短路径。在实际使用中,您需要将邻接矩阵替换为您的实际图形,并确定起点和终点。