当前位置:   article > 正文

弗洛伊德算法及代码实现_弗洛伊德算法代码

弗洛伊德算法代码

 使用邻接矩阵来存储图的信息,然后使用三重for循环实现弗洛伊德算法。

  1. #include <iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int inf = 1 << 26;
  7. int main()
  8. {
  9. int map[11][11];
  10. int m,n,i, j, w;
  11. for (int i = 1; i <= 10; i++) {
  12. for (int j = 1; j <= 10; j++) {
  13. if (i == j) map[i][j] = 0;
  14. else map[i][j] = inf;
  15. }
  16. }
  17. scanf("%d %d", &n, &m);
  18. for (int u = 1; u <= m; u++) {
  19. scanf("%d %d %d", &i, &j, &w);
  20. map[i][j] = w;
  21. map[j][i] = w;
  22. }
  23. for (int k = 1; k <= n; k++) {
  24. for (int i = 1; i <= n; i++) {
  25. if (map[i][k] == inf) continue;
  26. for (int j = 1; j <= n; j++) {
  27. if (i==j)continue;
  28. map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
  29. }
  30. }
  31. }
  32. for (int i = 1; i <= n; i++) {
  33. for (int j = 1; j <= n; j++) {
  34. cout << map[i][j] << " ";
  35. }
  36. cout << endl;
  37. }
  38. return 0;
  39. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/822058
推荐阅读
相关标签
  

闽ICP备14008679号