用c语言写有向图从某一点到所以点的最短路径长度
时间: 2023-05-29 20:06:51 浏览: 61
以下是使用Dijkstra算法实现的有向图从某一点到所有点的最短路径长度的C语言代码:
```
#include <stdio.h>
#include <limits.h>
#define V 6 // 图中顶点数
#define INF INT_MAX // 表示无穷大
// Dijkstra算法函数
void dijkstra(int graph[V][V], int start)
{
int dist[V]; // 存储最短路径长度
int visited[V] = {0}; // 标记顶点是否已访问
int i, j, min_dist, u;
// 初始化距离数组
for(i = 0; i < V; i++)
dist[i] = INF;
// 起点到自己的距离为0
dist[start] = 0;
// 找到从起点到其他顶点的最短路径
for(i = 0; i < V - 1; i++)
{
// 选择未访问过的距离最小的顶点
min_dist = INF;
for(j = 0; j < V; j++)
{
if(!visited[j] && dist[j] < min_dist)
{
min_dist = dist[j];
u = j;
}
}
// 标记该顶点已访问
visited[u] = 1;
// 更新相邻顶点的最短路径长度
for(j = 0; j < V; j++)
{
if(!visited[j] && graph[u][j] != INF && dist[u] + graph[u][j] < dist[j])
dist[j] = dist[u] + graph[u][j];
}
}
// 输出最短路径长度
printf("最短路径长度为:\n");
for(i = 0; i < V; i++)
{
printf("起点到顶点%d的最短路径长度为:%d\n", i, dist[i]);
}
}
// 主函数
int main()
{
int graph[V][V] = {{0, 1, INF, 3, INF, INF},
{INF, 0, INF, 2, INF, INF},
{INF, INF, 0, INF, INF, 4},
{INF, INF, INF, 0, 5, INF},
{INF, INF, INF, INF, 0, 6},
{INF, INF, INF, INF, INF, 0}}; // 有向图的邻接矩阵
int start = 0; // 起点
dijkstra(graph, start); // 调用Dijkstra算法
return 0;
}
```
上述代码中,邻接矩阵`graph`表示了一个有向图,其中`INF`表示两个顶点之间没有边相连。`start`表示起点,调用`dijkstra`函数即可计算出从该起点到所有顶点的最短路径长度。