如何修改上面的代码,使得FLoyd函数的参数是顶点数和两个顶点,最后得到的是这两个顶点间的最短路径,而不是任意两点间的
时间: 2024-04-12 12:27:08 浏览: 7
要修改Floyd函数的参数,使其计算指定两个顶点之间的最短路径,可以按照以下步骤进行修改:
1. 修改函数签名,将参数n改为顶点数,参数m删除。
2. 在Floyd函数中,将循环的范围修改为1到顶点数,而不是1到n。
3. 在Floyd函数中,将最短路径结果保存在dis数组中,不再需要tar数组。
下面是修改后的代码示例:
```cpp
void Floyd(int n, int start, int end) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dis[i] + e[k].cost < dis[j]) {
dis[j] = dis[i] + e[k].cost;
}
}
}
}
// 输出最短路径的结果
int cur = end;
int index = 0;
while (cur != start) {
path_length[index++] = cur;
cur = tar[cur];
}
printf("最短路径长度为:%d,路径为:", dis[end]);
printf("%d -> ", start);
for (int j = index - 1; j >= 0; j--) {
printf("%d -> ", path_length[j]);
}
printf("%d\n", end);
}
int main() {
int n = 13; // 图中顶点的个数
int m = 20; // 边的个数
// 初始化dis数组
memset(dis, INF, sizeof(dis));
// 构建图中的边
for (int i = 1; i <= m; i++) {
int u, v, w;
// 读入边的信息,包括始点u,终点v,代价w
scanf("%d%d%d", &u, &v, &w);
e[i].begin = u;
e[i].end = v;
e[i].cost = w;
e[i].next = head[u];
head[u] = i;
}
// 初始化源点到自身的最短距离为0
dis[1] = 0;
// 指定两个顶点,调用Floyd函数计算最短路径
int start = 1; // 起始顶点
int end = 4; // 终止顶点
Floyd(n, start, end);
return 0;
}
```
在这个修改后的代码中,我们通过指定起始顶点start和终止顶点end来调用Floyd函数。Floyd函数会计算出这两个顶点之间的最短路径,并输出结果。你可以根据需要修改起始顶点和终止顶点的值来计算不同的最短路径。