栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

图算法/最短路径 弗洛伊德

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

图算法/最短路径 弗洛伊德

弗洛伊德(floyd)

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);
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959615.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号