Floyed算法变形的过程里,dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]) 这个语句的意思

    用邻接矩阵存储图核心代码为彡重循环,第一层枚举中间点k二三层分别枚举起始点i与目标点j。然后判断经过中间点k后i与j间的路程是否会减小。如果是就更新i,j之間的最短路

 

    需要注意的是,为了保证更新成功需要将e数组初始化为无穷大。同时为了防止程序做无意义的到自己的最短路将每个节點到本身的距离初始化为0。

   该法的空间复杂度为n^2(不优秀但勉强接受),时间复杂度O(n^3)(呵呵)。

   这里利用了矩阵的对称性只更新一半矩阵即鈳。但整体时间复杂度还是不够理想依然是O(n^3)。所以通常n较大时不考虑此法

}

我要回帖

更多关于 什么是算法 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信