# 数据结构与算法-最短路径之Floyd算法

www.MyException.Cn  网友分享于：2013-10-08  浏览：0次

# 数据结构与算法--最短路径之Floyd算法

``````Dijkstra[] all = new Dijkstra[graph.vertexNum()];
for (int i = 0; i < all.length; i++) {
all[i] = new Dijkstra(graph, i);
}
for (int s = 0; s < all.length; s++) {
for (int i = 0; i < graph.vertexNum(); i++) {
System.out.print(s + " to " + i + ": ");
System.out.print("(" + all[s].distTo(i) + ") ");
System.out.println(all[s].pathTo(i));
}
System.out.println();
}``````

## 解决多源最短路径的Floyd算法

Floyd算法需要两个二维矩阵，因此使用邻接矩阵实现的有向加权图最为方便，不过我一直用邻接表实现的。为此需要将邻接表转换为相应的邻接矩阵。很简单，先将整个二维数组用0和正无穷填充，对角线上权值为0，其余位置正无穷。然后将邻接表中的元素覆盖原数组中对应位置的值，这样邻接表就转换为邻接矩阵了。邻接矩阵在代码中我们用`dist[][]`表示，这里面存放的就是任意顶点到其他顶点的最短路径！另外需要另外一个二维数组`edge[][]`，像`edge[v][w]`存放的是v到w的路径中途经的某一个顶点（或叫中转点），具体来说`edge[v][w]`表示v -> w这条路径上到w的前一个顶点。v -> w途径的顶点可能有多个，都在v那一行即`edge[v][i]`里找。

``````if (dist[v][k] + dist[k][w] < dist[v][w]) {
dist[v][w] = dist[v][k] + dist[k][w];
edge[v][w] = edge[k][w];
}``````

``````package Chap7;

import java.util.List;

public class Floyd {
private double[][] dist;
private int[][] edge;

public Floyd(EdgeWeightedDiGraph<?> graph) {
dist = new double[graph.vertexNum()][graph.vertexNum()];
edge = new int[graph.vertexNum()][graph.vertexNum()];
// 将邻接表变成了邻接矩阵
for (int i = 0; i < dist.length; i++) {
for (int j = 0; j < dist.length; j++) {
// 赋值给
edge[i][j] = i;
if (i == j) {
dist[i][j] = 0.0;
} else {
dist[i][j] = Double.POSITIVE_INFINITY;
}
}
}

for (int v = 0; v < graph.vertexNum(); v++) {
for (DiEdge edge : graph.adj(v)) {
int w = edge.to();
dist[v][w] = edge.weight();
}
}

for (int k = 0; k < graph.vertexNum(); k++) {
for (int v = 0; v < dist.length; v++) {
for (int w = 0; w < dist.length; w++) {
if (dist[v][k] + dist[k][w] < dist[v][w]) {
dist[v][w] = dist[v][k] + dist[k][w];
edge[v][w] = edge[k][w];
}
}
}
}
}

public boolean hasPathTo(int s, int v) {
return dist[s][v] != Double.POSITIVE_INFINITY;
}

public Iterable<Integer> pathTo(int s, int v) {
if (hasPathTo(s, v)) {
for (int i = v; i != s; i = edge[s][i]) {
path.push(i);
}
// 起点要加入
path.push(s);
return path;
}

return null;
}

public double distTo(int s, int w) {
return dist[s][w];
}

public static void main(String[] args) {
List<String> vertexInfo = List.of("v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7");
int[][] edges = {{4, 5}, {5, 4}, {4, 7}, {5, 7}, {7, 5}, {5, 1}, {0, 4}, {0, 2},
{7, 3}, {1, 3}, {2, 7}, {6, 2}, {3, 6}, {6, 0}, {6, 4}};

double[] weight = {0.35, 0.35, 0.37, 0.28, 0.28, 0.32, 0.38, 0.26, 0.39, 0.29,
0.34, 0.40, 0.52, 0.58, 0.93};

EdgeWeightedDiGraph<String> graph = new EdgeWeightedDiGraph<>(vertexInfo, edges, weight);
Floyd floyd = new Floyd(graph);
for (int s = 0; s < graph.vertexNum(); s++) {
for (int w = 0; w < graph.vertexNum(); w++) {
System.out.print(s + " to " + w + ": ");
System.out.print("(" + floyd.distTo(s, w) + ") ");
System.out.println(floyd.pathTo(s, w));
}
System.out.println();
}
}
}``````

``````// 初始化中
edge[i][j] = i;
// if条件中
edge[v][w] = edge[k][w];``````
• `edge[v][w]`存放的是v -> w路径中，终点w的前一个顶点。其实和深度优先和广度优先里用到的`edgeTo[]`差不多，这里的`edge[][]`对于任意一条v -> w的路径都是一个树形结构，从终点w开始不断往上找其父结点，最后到根结点（即起点v）处停止。
• `edge[i][j] = i;`一开始初始化为起点i的值。意思是i -> j路径中到j的前一个顶点就是i。也就是说我们先假设不经过任何其他顶点的从v到w的直接路径是最短的。在之后的循环中，如果经过其他顶点的i -> j更短就更新；否则就保持默认值。我们将看到，这样初始化在`edge[v][w] = edge[k][w]`这句中也适用。
``````[0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 2, 2]
[3, 3, 3, 3, 3, 3, 3, 3]
[4, 4, 4, 4, 4, 4, 4, 4]
[5, 5, 5, 5, 5, 5, 5, 5]
[6, 6, 6, 6, 6, 6, 6, 6]
[7, 7, 7, 7, 7, 7, 7, 7]``````
• 我们知道v -> k -> w的路径中，v -> k已经是最短路径了，所以只需要更新v -> w，从代码中也可以看出来，我们确实是只对`dist[v][w]``edge[v][w]`操作。但为什么是`edge[v][w] = edge[k][w]`？现在v -> k -> w这条路径更短，k -> w中到w的前一个顶点也就是v -> w路径中到w的前一个顶点。结合`edge[v][w]`的定义：存放的是v -> w路径中，w的前一个顶点，可得到`edge[v][w] = edge[k][w]`。画个图加深理解。

`edge[v][w] = edge[k][w] = k`，这里其实就是用了初始值而已。

``````[0, 5, 0, 7, 0, 4, 3, 2]
[6, 1, 6, 1, 6, 7, 3, 2]
[6, 5, 2, 7, 5, 7, 3, 2]
[6, 5, 6, 3, 6, 7, 3, 2]
[6, 5, 6, 7, 4, 4, 3, 4]
[6, 5, 6, 1, 5, 5, 3, 5]
[6, 5, 6, 7, 6, 7, 6, 2]
[6, 5, 6, 7, 5, 7, 3, 7]``````

by @sunhaiyu

2017.9.24