1. 介绍：
弗洛伊德算法和迪杰斯特拉算法一样，都是求最短路径的。迪杰斯特拉算法是求某一个顶点到其他各顶点的最短路径，而弗洛伊德算法会求出各个顶点到其他顶点的最短路径。弗洛伊德算法更简单，但是时间复杂度相对较高。同样以下图为例：
最短路径问题
假如有七个村庄(ABCDEFG)，有个人从G点出发，到其他六个村庄的最短路径分别是多少？到A、B、F、E只有一条路，没得选，但是到C有两条路，可以是2 + 7，也可以是8 + 4，到D点可以是3 + 9，也可以是6 + 4。图上标明了距离我们当然一看就知道怎么选，那么如何能让程序选择最短的路径呢？
2. 算法思想：
-
设置顶点vi到vk的最短路径为lik，顶点vk到vj的最短路径为lkj，顶点vi到vj的路径为lij。那么vi到vj的最短路径为：
min(lik + lkj, lij)。vk呢是图中的任意一点，这样就可以算出vi到vj的最短路径了。 -
其他顶点之间的最短路径用同样的方式求得。
3. 案例：
以上图为例，步骤如下：
- 初始化邻接矩阵，自己和自己用0表示，连不通的用N表示。如下：
A B C D E F G
A{0, 5, 7, N, N, N, 2},
B{5, 0, N, 9, N, N, 3},
C{7, N, 0, N, 8, N, N},
D{N, 9, N, 0, N, 4, N},
E{N, N, 8, N, 0, 5, 4},
F{N, N, N, 4, 5, 0, 6},
G{2, 3, N, N, 4, 6, 0}
- 然后还要用一个数组来初始化顶点的前驱关系，其实叫前驱关系可能不太好理解，可以理解为保存一条路径的中间顶点。看了后面的例子就会明白。初始情况如下：
A B C D E F G
A{A, A, A ,A, A, A, A},
B{B, B, B ,B, B, B, B},
C{C, C, C, C, C, C, C},
D{D, D, D, D, D, D, D},
E{E, E, E, E, E, E, E},
F{F, F, F, F, F, F, F},
G{G, G, G, G, G, G, G}
- 在第一轮循环中，以A顶点当作中间顶点的所有情况进行遍历，然后更新上面的两个二维数组。把A作为中间顶点到底是啥意思？看下面的路径：
C --> A --> G：9
C --> A --> B：12
G --> A --> B：7
上面这3条路径，A在中间，这个就叫做以A为中间顶点的情况。那么程序要如何找到这三条路径呢？我们搞三个数组，一个表示中间顶点数组，一个表示出发顶点数组，一个表示终点数组，如下：
中间顶点：["A", "B", "C", "D", "E", "F", "G"]
出发顶点：["A", "B", "C", "D", "E", "F", "G"]
终点：["A", "B", "C", "D", "E", "F", "G"]
然后三层for循环遍历这个三个数组，看看以第一层循环中的顶点为中间顶点的路径有多少条。
- 先看第一条以A为中间顶点的路径，C到G的距离为9，原先C到G的距离是N，9小于N，所以更新该值，因为是无向图，所以G到C的距离也更新为9；同理更新C到B，B到C。但是G到B，B到G的距离不能更新，因为原先的3比现在的7更小。所以更新后的数组为：
A B C D E F G
A{0, 5, 7, N, N, N, 2},
B{5, 0, 12, 9, N, N, 3},
C{7, 12, 0, N, 8, N, 9},
D{N, 9, N, 0, N, 4, N},
E{N, N, 8, N, 0, 5, 4},
F{N, N, N, 4, 5, 0, 6},
G{2, 3, 9, N, 4, 6, 0}
上面更新了距离的地方，都用到了A作为中间顶点，所以，将前驱关系表中对应位置的字母都更新成A，所以就变成了：
A B C D E F G
A{A, A, A ,A, A, A, A},
B{B, B, A ,B, B, B, B},
C{C, A, C, C, C, C, A},
D{D, D, D, D, D, D, D},
E{E, E, E, E, E, E, E},
F{F, F, F, F, F, F, F},
G{G, G, A, G, G, G, G}
3. 代码实现：
public class FloydDemo {
private static final int N = 999;
public static void main(String[] args) {
String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
int[][] edges = {
{0, 5, 7 ,N, N, N, 2},
{5, 0, N ,9, N, N, 3},
{7, N, 0 ,N, 8, N, N},
{N, 9, N ,0, N, 4, N},
{N, N, 8 ,N, 0, 5, 4},
{N, N, N ,4, 5, 0, 6},
{2, 3, N ,N, 4, 6, 0}
};
Graph graph = new Graph(vertexs, edges);
graph.floyd();
graph.printArr();
}
}
class Graph{
String[] vertexs; // 存放顶点
int[][] edges; // 邻接矩阵，存放边，也是存放距离
int[][] pre; // 前驱顶点
/**
* 构造器
* @param vertexs
* @param edges
*/
public Graph(String[] vertexs, int[][] edges) {
this.vertexs = vertexs;
this.edges = edges;
this.pre = new int[vertexs.length][vertexs.length];
for (int i=0; i<vertexs.length; i++) {
Arrays.fill(pre[i], i);
}
}
/**
*
*/
public void floyd() {
int len = 0;
for (int k=0; k<vertexs.length; k++) {
for (int i=0; i<vertexs.length; i++) {
for (int j=0; j<vertexs.length; j++) {
len = edges[i][k] + edges[k][j];
if (len < edges[i][j]) {
edges[i][j] = len;
pre[i][j] = pre[k][j];
}
}
}
}
}
/**
* 打印数组
*/
public void printArr() {
System.out.println("distance: ");
for (int i=0; i<edges.length; i++) {
System.out.println(Arrays.toString(edges[i]));
}
System.out.println("pre: ");
for (int i=0; i<pre.length; i++) {
System.out.println(Arrays.toString(pre[i]));
}
}
}
这个代码还是很好理解的，可能有小伙伴发现了，pre数组好像没啥用，去掉了也可以求得最短路径。没错，是可以得到顶点到另一个顶点的最短路径的值，但是不知道具体路径是哪一条。pre数组就是用来记录路径的。
网友评论