Question

最短路径算法 C语言

1，给出的数据为一个网络（如图只是一部分，一共108个节点，txt）；数据有有两列，每一行的两个数字代表这两个节点相连，这是一个无向的网络。
2，现在需要使用最短路径算法，算出每个节点之间的最短路径，然后用一个二维数组path[108][108]（规模108*108）保存每个节点之间的最短路径的数值，一定要用数组保存！
求助！追加。
3，这是无权图，可以视作节点之间的权为1。

Answer 1

#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写给我。

Answer 2

为了不坑害求知的少年，我决定不给你写代码。去网上搜下关键字“任意节点最短路径”，你会发现有无数的源码。这些代码基本上都源于两个算法：floyd算法，Dijkstra算法。
使用floyd算法求最简单，代码大概8行左右，很简单吧，呵呵，核心就是3个for循环而已。

追问

跪求坑害。。。。。。

追答

#include <stdio.h>

#define  MAX_PATH_LENGTH 1000000
#define  MAX_VECTOR_SIZE 108
int main()
{
int path[MAX_VECTOR_SIZE][MAX_VECTOR_SIZE];
int preNode = 0;
int nextNode = 0;
FILE *pfile = NULL;
int i = 0;
int j = 0;
int k = 0;
//初始化
for(i=0;i<MAX_VECTOR_SIZE;i++)
{
for(j=0;j<MAX_VECTOR_SIZE;j++)
{
path[i][j]=MAX_PATH_LENGTH;
}
}
for(i = 0; i<MAX_VECTOR_SIZE; i++)
{
path[i][i]=0;
}
//从文件中读入数据
pfile = fopen("test.txt","r");
if(pfile == NULL)
{
printf("ERROR!\n");
return 0;
}
while(fscanf(pfile,"%d%d",&preNode,&nextNode)!=EOF)
{
path[preNode-1][nextNode-1] = 1;
path[nextNode-1][preNode-1] = 1;
}
//使用floyd算法计算任意两点之间的距离
for(i=0;i<MAX_VECTOR_SIZE;i++)
{
for(j=0;j<MAX_VECTOR_SIZE;j++)
{
for(k=0;k<MAX_VECTOR_SIZE;k++)
{
if(path[i][k]!=MAX_PATH_LENGTH && path[k][j]!=MAX_PATH_LENGTH)
{
if(path[i][j]>path[i][k]+path[k][j])
{
path[i][j] = path[i][k]+path[k][j];
}
}
}
}
}
//打印结果
for(i=0;i<MAX_VECTOR_SIZE;i++)
{
for(j=0;j<MAX_VECTOR_SIZE;j++)
{
printf("%d ",path[i][j]);
}
printf("\n");
}
return 0;
}

追问

亲，我用VC运营后，结果是这样的。

追答

自己修改下”打印代码“就行了。

追问

哪里有错呢。我看了代码后面的打印段 貌似是对的呢。

追答

1-确定你把输入文件放在跟源代码文件放在同一个目录下，且输入文件命名是”test.txt"。

2-明白1000000的含义，这个值定义在

#define  MAX_PATH_LENGTH 1000000

1000000这个值出现的意义是该两点之间路径不通。0表示该点是自己到自己的距离。

追问

我这边打印出来的结果有点小问题。
例如1到2，2到8，（没有直接的1到8），
所以1-8的最短距离应该为2啊。但是显示是1000000
能加个Q吗 大神

追答

哎呀！忘了说了，你有108个点，但是你只申请了108个空间的数组。那么在查询a点到b点的距离时，你应该查的是path[a-1][b-1]。

追问

请问preNode和nextNode是什么意思呢。
为什么要这么写啊

追答

你读文件一行不是两个数字不是代表两个点吗？前一个点，后一个点呗。