迪杰斯特拉算法的C语言代码实现
时间: 2023-10-28 10:06:43 浏览: 127
你可以使用以下代码实现迪杰斯特拉算法的C语言实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define V 9 // 顶点的数量
// 找到dist数组中最小距离的顶点的索引
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (sptSet[v == false && dist[v <= min) {
min = dist[v];
min_index = v;
}
}
return min_index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V]; // 存储从源到每个顶点的最短距离
bool sptSet[V]; // sptSet[i为true表示顶点i已经在最短路径树上
// 初始化所有的距离为无穷大,sptSet都为false
for (int i = 0; i < V; i++) {
dist[i = INT_MAX;
sptSet[i = false;
}
dist[src = 0; // 源到自身的距离为0
for (int count = 0; count < V-1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u = true;
for (int v = 0; v < V; v++) {
if (!sptSet[v && graph[u][v && dist[u != INT_MAX && dist[u + graph[u][v < dist[v]) {
dist[v = dist[u + graph[u][v];
}
}
}
// 打印最短路径
printf("顶点\t\t最短距离\n");
for (int i = 0; i < V; i++) {
printf("%d\t\t%d\n", i, dist[i]);
}
}
int main() {
int graph[V][V = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}
```
该代码实现了迪杰斯特拉算法,通过计算从源顶点到其他顶点的最短路径。你可以将你的图形表示成一个邻接矩阵,其中`graph[i][j]`表示顶点i到顶点j之间的边的权重。当运行代码时,它将打印出每个顶点到源顶点的最短距离。
阅读全文