一、问题
解决图中最短路径问题
二、解法
1、思想总结：
从i到j的最短路径有两种情况，要么ij直连结果即为D(i,j)，要么经过若干个中间点k，即D(i, k) + D(k, j)，然后哪个小结果就是哪个
下一次遍历中间点时要保证之前的中间点都已经便利过。
2、需要的参数
i顶点
j目标点
k中间转折点
3、状态转移矩阵：f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])
4、另十字交叉法
横线和竖线为中间点k
对角线为本点到本点的距离
（1）第一次算不包含线上的点与线上的点组成的二阶矩阵，算A10+A00+A00+A01与A11进行比较。每次更新矩阵
第一次结果不变
（2）第二次
以此类推
5、code
package algorithm;
public class Floyd {
private int n;
private class Graph {
int[][] edges;
char[] vertex;
}
void floyd(Graph g) {
int[][] A = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = g.edges[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
A[i][j] = Math.min(A[i][j], A[i][k] + A[k][j]);
}
}
}
}
原文链接：https://www.qiquanji.com/post/8105.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知