C语言最短路径算法问题，Floyd算法行不通

Python015

C语言最短路径算法问题，Floyd算法行不通,第1张

要用算法你也要先理解了再用啊，不懂你是修改了什么，反正floyd肯定不是你这么写，floyd要把中间结点的遍历放在最三重循环的最外层。另外，求最短路径是怎么走的完全可以在更新最短路径长度的过程中记录中间结点是什么，这并非算法不能解决，而在于使用算法的人是否真正懂得算法过程，以及待解决的问题是否需要求解这方面的问题。

floyd是动态规划的简化,所以输出路径一样套用dp的典型记录方式即可.

即,每次松弛时,记录是松弛了哪一个点.然后输出时递归输出即可.

弄一个矩阵R[][]初始化为0,然后比如你的距离矩阵是D[][]

松弛改为是:

if(D[i][j] >D[i][k]+D[k][j]){

D[i][j] = D[i][k]+D[k][j]

R[i][j] = k

}

输出时可以写一个递归函数

function out(a,b){

if(R[a][b] == 0){

return

}

out(a,R[a][b])

//输出k

out(R[a][b],b)

}

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