本博客只做代码训练, 理论阅读请直接点
https://www.cnblogs.com/ECJTUACM-873284962/p/6995648.html
解决图中最短路径问题
一, 解法
核心思想是 DP.
i 顶点
j 目标点
k 经过的点
状态转移矩阵: f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k]+f[k-1][k][j])
- 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]);
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2948065.html