{
int G[100][100] = {}
//一个记录图的邻接矩阵
int a, b, w
//输入一共有7条边, 5个点
int i, j, k
for(i = 1i <= 5i++)
for(j = 1j <= 5j++)
G[i][j] = 9999999
for(i = 1i <= 7i++)
{
scanf("%d %d %d", &a, &b, &w)//输入每条边的信息,a和b代表这条边的两个顶点w代表两个点的距离
G[a][b] = w
G[b][a] = w
}
for(k = 1k <= 5k++)
for(i = 1i <= 5i++)
for(j = 1j <= 5j++)
if(G[i][j] >G[i][k] + G[k][j])
G[i][j] = G[i][k] + G[k][j]
printf("%d", G[1][4])//输出两点之间的最短路,这里的两个点是3和5
return 0
}
G[i][j]代表i到j的距离,甲,乙,丙,丁,戊用1,2,3,4,5代替
如果你还不懂的话,就看一些关于图论的问题,这个最短路是图论中的一个经典题
#include <stdio.h>
#define MAXNODE 108
int path[MAXNODE + 1][MAXNODE + 1] = {0}
int main(void)
{
FILE *fpr, *fpw
int va, vb, i, j, k
fpr = fopen("in.txt", "r") /* 读取的文件名称in.txt */
fpw = fopen("out.txt", "w") /* path的数据在out.txt中展现 */
while (fscanf(fpr, "%d%d", &va, &vb) != EOF)
path[va][vb] = path[vb][va] = 1
for (k = 1 k <= MAXNODE ++k) {
for (i = 1 i <= MAXNODE ++i) {
for (j = 1 j <= MAXNODE ++j) {
if (!path[i][k] || !path[k][j])
continue
if (!path[i][j])
path[i][j] = path[i][k] + path[k][j]
else if (path[i][j] > path[i][k] + path[k][j])
path[i][j] = path[i][k] + path[k][j]
}
}
}
for (i = 1 i <= MAXNODE ++i) {
for (j = 1 j <= MAXNODE ++j) {
if (i == j)
fprintf(fpw, "%-10d", 0)
else if (path[i][j])
fprintf(fpw, "%-10d", path[i][j])
else
fprintf(fpw, "%-10d", -1)
}
fprintf(fpw, "\n")
}
return 0
}
注意:floyd算法中k为最外层,这是动态规划的思想,不能改变i,j,k的顺序!!!
这是之前的答案的错误之处。
-1表示不通。
具体程序分析,我可以加你QQ,愿意的话,你把QQ写给我。