dijkstra算法c语言实现
时间: 2023-09-26 20:08:57 浏览: 59
以下是Dijkstra算法的C语言实现:
```c
#include <stdio.h>
#include <limits.h>
// 定义顶点数和边的数量
#define V 6
#define E 9
// 定义一个函数,用于找到当前未包含在最短路径中的距离源点最短的顶点
int minDistance(int distance[], bool shortestPathSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (shortestPathSet[v] == false && distance[v] <= min)
min = distance[v], min_index = v;
return min_index;
}
// 定义一个函数,用于打印最短路径的结果
void printSolution(int distance[])
{
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, distance[i]);
}
// 定义一个函数,用于实现Dijkstra算法并计算最短路径
void dijkstra(int graph[V][V], int src)
{
int distance[V]; // 存储从源顶点到其他顶点的最短距离
bool shortestPathSet[V]; // shortestPathSet[i]为true表示顶点i已经在最短路径中
// 初始化所有顶点的距离为无穷大,且都不在最短路径中
for (int i = 0; i < V; i++)
distance[i] = INT_MAX, shortestPathSet[i] = false;
distance[src] = 0; // 源点到自身的距离为0
// 找到未包含在最短路径中的距离源点最短的顶点,并将其添加到最短路径中
for (int count = 0; count < V - 1; count++) {
int u = minDistance(distance, shortestPathSet);
shortestPathSet[u] = true;
// 更新当前选定顶点的邻接顶点的距离
for (int v = 0; v < V; v++)
if (!shortestPathSet[v] && graph[u][v] && distance[u] != INT_MAX
&& distance[u] + graph[u][v] < distance[v])
distance[v] = distance[u] + graph[u][v];
}
printSolution(distance);
}
int main()
{
int graph[V][V] = {{0, 4, 0, 0, 0, 0},
{4, 0, 8, 0, 0, 0},
{0, 8, 0, 7, 0, 4},
{0, 0, 7, 0, 9, 14},
{0, 0, 0, 9, 0, 10},
{0, 0, 4, 14, 10, 0}};
dijkstra(graph, 0);
return 0;
}
```
上面的代码实现了Dijkstra算法,并计算了给定图形中的最短路径。
相关推荐
![pages](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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_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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)