Floyd算法求有权图（非负权）的最短路径并打印

wangxinarhat 发布于2019-08-16 18:34 / 1408人阅读

摘要：网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。结合大佬的回答和自己的搜索，找到一篇还不错的证明和原理分析的文章。

状态转移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i思路对于每一个k(i

public class FloydTest {
  private static int[][] matrix;

  private static int[][] path;

  public static void main(String[] args) {

    initMatrixAndPath(
            new int[][]{
                    {0, 1, 8, 5},
                    {1, 0, 7, 6},
                    {8, 7, 0, 2},
                    {5, 6, 2, 0}}
    );


    floyd(matrix, path);
    printShortDistance();
    printShortDistanceDetail();
  }

  private static void initMatrixAndPath(int[][] matrix) {
    FloydTest.matrix = matrix;
    FloydTest.path = new int[matrix.length][matrix.length];

    for (int i = 0; i < FloydTest.matrix.length; i++) {
      for (int j = 0; j < FloydTest.matrix[i].length; j++) {
        path[i][j] = j;
      }
    }
  }

  private static void floyd(int[][] matrix, int[][] path) {
    for (int k = 0; k < matrix.length; k++) {
      for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix.length; j++) {
          if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
            matrix[i][j] = matrix[i][k] + matrix[k][j];
            path[i][j] = path[i][k];
          }
        }
    }


  }

  private static String getNodeName(int nodeIndex) {
    return "v" + nodeIndex;
  }

  private static void printShortDistanceDetail() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        int x = j;
        StringBuilder sb = new StringBuilder("最短路径[v" + i + ",v" + j + "]为:");
        sb.append(getNodeName(x));
        sb.append("<--");
        while (path[i][j] != x) {
          x = path[i][x];
          sb.append(getNodeName(path[i][x]));
          sb.append("<--");
        }
        sb.append(getNodeName(i));

        System.out.println(sb);
      }

    }
  }

  private static void printShortDistance() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        System.out.println("v" + i + "到" + "v" + j + "最短路径为:" + matrix[i][j]);
      }
    }
  }
}

输出结果

v0到v0最短路径为:0
v0到v1最短路径为:1
v0到v2最短路径为:7
v0到v3最短路径为:5
v1到v0最短路径为:1
v1到v1最短路径为:0
v1到v2最短路径为:7
v1到v3最短路径为:6
v2到v0最短路径为:7
v2到v1最短路径为:7
v2到v2最短路径为:0
v2到v3最短路径为:2
v3到v0最短路径为:5
v3到v1最短路径为:6
v3到v2最短路径为:2
v3到v3最短路径为:0
最短路径[v0,v0]为:v0<--v0
最短路径[v0,v1]为:v1<--v0
最短路径[v0,v2]为:v2<--v3<--v0
最短路径[v0,v3]为:v3<--v0
最短路径[v1,v0]为:v0<--v1
最短路径[v1,v1]为:v1<--v1
最短路径[v1,v2]为:v2<--v1
最短路径[v1,v3]为:v3<--v1
最短路径[v2,v0]为:v0<--v3<--v2
最短路径[v2,v1]为:v1<--v2
最短路径[v2,v2]为:v2<--v2
最短路径[v2,v3]为:v3<--v2
最短路径[v3,v0]为:v0<--v3
最短路径[v3,v1]为:v1<--v3
最短路径[v3,v2]为:v2<--v3
最短路径[v3,v3]为:v3<--v3

其他：看了网上的一些关于floyd算法证明的过程。其实最主要的一点，证明当k为遍历的最后一个节点时，d(i,k)+d(k,j)取最小值，d(i,k)和d(k,j)也已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。

ps:结合大佬的回答和自己的搜索，找到一篇还不错的证明和原理分析的文章。
https://www-m9.ma.tum.de/grap...

云服务器 GPU云服务器最经典的最短路径算法非负权 floyd算法最短路问题算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75362.html

【程序员必会十大算法】之弗洛伊德算法

摘要：学习资料迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径代码不能设置为，否则两个相加会溢出导致出现负权创建顶点和边学习资料迪杰斯特拉计算的是单源最...

JellyBool 2021-09-30 09:47 评论0 收藏0
单源点最短路径(Bellman-Ford)原理及js实现

摘要：说明算法运行结束后，会得到从源节点到其它所有节点的最短路径，同时得到每个节点的前驱节点，不能包含负权回路如图但可以包含图，这里所说的负权环路是指环路的权值总和为正或为负图图松弛操作概念松弛操作针对的操作对象是图中的边，对图中任意一条边， 1. 说明 Bellman-Ford算法运行结束后，会得到从源节点 s 到其它所有节点的最短路径，同时得到每个节点的前驱节点，Bellman-Ford...

Michael_Lin 2019-08-21 18:37 评论0 收藏0
最短路径算法总结

摘要：对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过，边数不会超过。我会说只有三个吗适用于任何图，不管有向无向，边权正负，但是最短路必须存在。定义（还记得这些定义吗？如果对图的概念和存储不了解请点击链接）路径最短路有向图中的最短路、无向图中的最短路单源最短路、每对结点之间的最短路性质对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。对于边权为正的图，任意...

Tecode 2022-06-28 19:00 评论0 收藏0
【程序员必会十大算法】之迪杰斯特拉算法

摘要：推荐资料推荐学习文章代码不能设置为否则两个相加会溢出导致出现负权创建顶点和边创建图顶点数得到边的数目调用算法计算最短路径推荐资料推荐学习文章代码 public...

番茄西红柿 2021-09-29 09:35 评论0 收藏2637
王者编程大赛之五 — 最短路径

摘要：由于是从顶点到的最短路径，则有。算法流程根据最短路径的最优子结构性质，提出了以最短路径长度递增，逐次生成最短路径的算法。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之三背包王者编程大赛之四约瑟夫环首发于樊浩柏科学院自如年底就会拥有 50W 间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电、家具...

yuanzhanghu 2019-07-01 12:36 评论0 收藏0