用c语言读入一个有向图的带权邻接矩阵(即数组表示),建立有向图出源点至每一个其它顶点的最短路径长度。输入的第一行包含2个正整数n和s,表示图中共有n个顶点,且源点为s。其中n不超过50,s小于n。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数,如果大于0,则表示第i个顶点有指向第j个顶点的有向边,且权值为对应的整数值;如果这个整数为0,则表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为0。 输出 只有一行,共有n-1个整数,表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径,输出-1。 请注意行尾输出换行。
时间: 2024-03-03 10:50:32 浏览: 86
有向图邻接表的建立,深度广度搜索及拓扑排序.zip_45V_bfs_dfs_有向图
5星 · 资源好评率100%
好的,我明白了。这是一个比较经典的最短路径问题,可以使用Dijkstra算法或者Floyd算法来解决。我这里给你提供一个使用Dijkstra算法的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 50
int n, s;
int graph[MAX_N][MAX_N];
int dist[MAX_N];
_Bool visited[MAX_N];
void dijkstra() {
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[s] = 0;
for (int i = 0; i < n - 1; i++) {
int min_dist = INT_MAX;
int min_idx = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_idx = j;
}
}
if (min_idx == -1) {
break;
}
visited[min_idx] = 1;
for (int j = 0; j < n; j++) {
if (graph[min_idx][j] > 0 && dist[min_idx] != INT_MAX && dist[min_idx] + graph[min_idx][j] < dist[j]) {
dist[j] = dist[min_idx] + graph[min_idx][j];
}
}
}
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
dijkstra();
for (int i = 0; i < n; i++) {
if (i != s) {
if (dist[i] == INT_MAX) {
printf("-1\n");
} else {
printf("%d\n", dist[i]);
}
}
}
return 0;
}
```
这个程序中,我们使用了一个dist数组来记录源点到每个顶点的最短距离,使用一个visited数组来标记每个顶点是否已经被访问过。在每次循环中,找到未访问过的距离最小的顶点,并将其标记为已访问过。然后,遍历与这个顶点相邻的顶点,更新它们的最短距离。最后,输出源点到其它每个顶点的最短距离。如果某个顶点无法到达,则输出-1。
注意,这个程序中使用了一个_INT_MAX常量来表示一个非常大的整数,用于表示某个顶点到源点的距离还没有被计算出来。如果你的编译器不支持这个常量,你需要自己定义一个非常大的数来代替它。
阅读全文