怎么看网站是哪家公司做的,租凭境外服务器做违规网站,西安建设和住房保障局网站,网站建设科技北京有限公司时间复杂度#xff1a;O(n^3)
使用场景#xff1a;当需要得知任意两个点的最短距离以及其路径时使用
准备#xff1a;需要两个矩阵
一个记录最短距离#xff08;D#xff09;
一个记录最短路径的最后一个结点#xff08;P#xff09;
其核心在于不断的判断越过中间…时间复杂度O(n^3)
使用场景当需要得知任意两个点的最短距离以及其路径时使用
准备需要两个矩阵
一个记录最短距离D
一个记录最短路径的最后一个结点P
其核心在于不断的判断越过中间结点是否比不越过中间节点距离更短迭代的结果也会影响到后面的路径的更新通过不断的更新使得每两个节点直接的距离被都更新到最短
具体过程 1.初始化 D,P 矩阵D 矩阵初始化为所有结点的入度距离P 矩阵 初始化为所有结点的入度结点 int MAX Integer.MAX_VALUE;int[][] D {{MAX,MAX,MAX,MAX, 6},{ 9,MAX, 3,MAX,MAX},{ 2,MAX,MAX, 5,MAX},{MAX,MAX,MAX,MAX, 1},{MAX,MAX,MAX,MAX,MAX}};int[][] P {{-1,-1,-1,-1, 0},{ 1,-1, 1,-1,-1},{ 2,-1,-1, 2,-1},{-1,-1,-1,-1, 3},{-1,-1,-1,-1,-1}};
2.将每一个点都做一次中间结点
3.在当前中间节点的基础上遍历所有结点更新最短路
关于两个矩阵更新规则
D: 根据上一次的 D ,若 遍历到的结点到中间结点 中间结点到目标结点 上一次遍历到的结点到目标结点就更新P: 若 D 发生变动则将路径更新为 上一次 中间结点到目标节点的路径
共五个结点故我们需要重复 5 次 2,3 步骤
public static void main(String[] args) {int MAX Integer.MAX_VALUE/2;int[][] D {{MAX,MAX,MAX,MAX, 6},{ 9,MAX, 3,MAX,MAX},{ 2,MAX,MAX, 5,MAX},{MAX,MAX,MAX,MAX, 1},{MAX,MAX,MAX,MAX,MAX}};int[][] P {{-1,-1,-1,-1, 0},{ 1,-1, 1,-1,-1},{ 2,-1,-1, 2,-1},{-1,-1,-1,-1, 3},{-1,-1,-1,-1,-1}};for(int k0;k5;k) {//中间结点 //遍历所有的结点对for(int i0;i5;i) {for(int j0;j5;j) {if(D[i][k] D[k][j] D[i][j]) {D[i][j] D[i][k] D[k][j];P[i][j] P[k][j];}}}}} 当中间点为 0 时,两个矩阵的更新结果为 [∞, ∞, ∞, ∞, 6] [9, ∞, 3, ∞, 15] [2, ∞, ∞, 5, 8] [∞, ∞, ∞, ∞, 1] [∞, ∞, ∞, ∞, ∞] --------------------------------- [-1, -1, -1, -1, 0] [1, -1, 1, -1, 0] [2, -1, -1, 2, 0] [-1, -1, -1, -1, 3] [-1, -1, -1, -1, -1] 当中间点为 1 时,两个矩阵的更新结果为 [∞, ∞, ∞, ∞, 6] [9, ∞, 3, ∞, 15] [2, ∞, ∞, 5, 8] [∞, ∞, ∞, ∞, 1] [∞, ∞, ∞, ∞, ∞] --------------------------------- [-1, -1, -1, -1, 0] [1, -1, 1, -1, 0] [2, -1, -1, 2, 0] [-1, -1, -1, -1, 3] [-1, -1, -1, -1, -1] 当中间点为 2 时,两个矩阵的更新结果为 [∞, ∞, ∞, ∞, 6] [5, ∞, 3, 8, 11] [2, ∞, ∞, 5, 8] [∞, ∞, ∞, ∞, 1] [∞, ∞, ∞, ∞, ∞] --------------------------------- [-1, -1, -1, -1, 0] [2, -1, 1, 2, 0] [2, -1, -1, 2, 0] [-1, -1, -1, -1, 3] [-1, -1, -1, -1, -1] 当中间点为 3 时,两个矩阵的更新结果为 [∞, ∞, ∞, ∞, 6] [5, ∞, 3, 8, 9] [2, ∞, ∞, 5, 6] [∞, ∞, ∞, ∞, 1] [∞, ∞, ∞, ∞, ∞] --------------------------------- [-1, -1, -1, -1, 0] [2, -1, 1, 2, 3] [2, -1, -1, 2, 3] [-1, -1, -1, -1, 3] [-1, -1, -1, -1, -1] 当中间点为 4 时,两个矩阵的更新结果为 [∞, ∞, ∞, ∞, 6] [5, ∞, 3, 8, 9] [2, ∞, ∞, 5, 6] [∞, ∞, ∞, ∞, 1] [∞, ∞, ∞, ∞, ∞] --------------------------------- [-1, -1, -1, -1, 0] [2, -1, 1, 2, 3] [2, -1, -1, 2, 3] [-1, -1, -1, -1, 3] [-1, -1, -1, -1, -1] 4.若最后需要得到最短路路径可以通过 先找到 路径矩阵的位置得到前一个点再找到该点与前一个点的前一个点直到前一个点变成自身为止 如我们要找到 v1 到 v0 的最短路径 先找到 1 - 0 的最近的前一个结点,也就是 P[1][0] 2 得知了前一个结点为 2 记录路径 2 - 0 继续往前找1 - 2 的前一个结点也就是 P[1][2] 1 得知了前一个结点为 1记录路径 1 - 2 - 0 再继续往前就是寻找 1 - 1 自己找自己的时候就代表路径已经完整了 故 v1 到 v0 的最短路径为 1 - 2 - 0
