最近在看网络的一些基础知识, 提到了floyd解决更新路由表计算最短路径, 从这个角度来理解floyd算法
在这个算法中每个路由器是知道总体全局信息的. 每个路由器知道自己和邻居的距离, 每个路由器定时将自己知道的路由表同步给相邻的路由器. 每个路由器接收到发送过来的路由表, 计算到每个路由器的距离
void floyd(int[][] a) { // path[i][j] 表示从i到j的路径中, j的上一个顶点, floyd计算的是每个顶点到其他顶点的最优路径 int[][] path = new int[a.length][a.length]; // 保存路径 for(int i=0; i<a.length; i++) { for(int j=0; i<a.length; i++) { if (i == j) { path[i][j] = -1; } else { // 如果i->j路径可达 if (a[i][j] < INF) { // i->j路径上, j的上一个节点是i path[i][j] = i; } else { path[i][j] = -1; } } } } // 传播节点k的路由表 for(int k=0; k<a.length; k++) { // 传播给i节点 for(int i=0; i<a.length; i++) { // 通过路由表, 重新计算i节点到j节点的最优路径 for(int j=0; j<a.length; j++) { // 原先节点i到j的距离是a[i][j], 如果a[i][k] + a[j][k] < a[i][j]那么我们就更新i到j的距离 if(a[i][k] + a[j][k] < a[i][j]) { // 更新i到j的代价 a[i][j] = a[i][k] + a[j][k]; // 更新i->j路径中j的前一个节点就是k->j这条路径中j的上一个节点 path[i][j] = path[k][j]; } } } } }