floyd 多源最短路径 O(n^3)
- 最短路径
- 弗洛伊德算法
- 是一种动态规划算法
- 动态规划数组
- 思想是:点i到点j经过k会不会更近一点
- 动态规划数组
- as[i][j]
package xcrj.kchalgorithm.graphAlgorithm;
import xcrj.kchalgorithm.graphAlgorithm.graph.MGraph;
import xcrj.kchalgorithm.graphAlgorithm.graph.MVertex;
public static void initialize(int n) {
as = new int[n][n];
path = new int[n][n];
}
public static void floyd(MGraph graph, int n) {
// 初始化as和path
for (int i = 0; i < graph.getN(); i++) {
for (int j = 0; j < graph.getN(); j++) {
as[i][j] = graph.getEdges()[i][j];
// 先全部置为不可达
path[i][j] = -1;
}
}
// 点i到点j经过k会不会更近一点
for (int k = 0; k < graph.getN(); k++) {
for (int i = 0; i < graph.getN(); i++) {
for (int j = 0; j < graph.getN(); j++) {
if (as[i][j] > as[i][k] + as[k][j]) {
as[i][j] = as[i][k] + as[k][j];
path[i][j] = k;
}
}
}
}
}
public static void showMinPath(int start, int end) {
// 最短路径长度
StringBuilder sb = new StringBuilder(10);
sb.append("点").append(start).append("到").append("点").append(end).append("的最短路径是").append(as[start][end]);
System.out.println(sb);
// 最短路径经过的点,start到end经过了k,从k点开始继续往下走
StringBuilder sb1 = new StringBuilder(8);
while (-1 != start && start != end) {
sb1.append(start).append("->");
start = path[start][end];
}
sb1.append(end);
System.out.println(sb1);
}
public static void main(String[] args) {
// 构建无向带权图
int n = 5;
int e = 6;
MVertex[] mVertices = new MVertex[n];
for (int i = 0; i < n; i++) {
mVertices[i] = new MVertex(i, (char) i);
}
int[][] edges = new int[n][n];
edges[0][4] = 6;
edges[4][0] = 6;
edges[0][1] = 9;
edges[1][0] = 9;
edges[1][2] = 3;
edges[2][1] = 3;
edges[0][2] = 2;
edges[2][0] = 2;
edges[2][3] = 5;
edges[3][2] = 5;
edges[3][4] = 1;
edges[4][3] = 1;
// 不可达认为是10000,比edges中所有的权值都大
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (0 == edges[i][j]) edges[i][j] = 10000;
}
}
MGraph mGraph = new MGraph(n, e, mVertices, edges);
// 初始化
initialize(n);
// 调用Floyd
floyd(mGraph, n);
// 点0到点3的最短路径
showMinPath(0, 3);
}
}



