动态规划法(二)——弗洛伊德算法

问题描述

给定一个带权有向图,计算任意两结点间的最短路径。

迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉算法即可求的任意两结点间的最短路径。迪杰斯特拉算法的时间复杂度为O(n^2),因此采用这种方法的时间复杂度为O(n^3)。 但是,迪杰斯特拉算法不允许权值为负数,因此需要使用弗洛伊德算法。 弗洛伊德算法允许权值为负数的边,但不允许回路的路径长度为负数。因为,若回路长度为负数,那么走一次回路,路径长度一定比上一次小,故这个问题就没有意义了。

数据结构

  • dis: Map<String, Map<String,Integer>> dis; 这是一个二维数组,存储两个结点间的最短路径长度。 Map中的key表示起点的编号; Map中的value是一个Map< String,Integer>类型的集合,表示以key为起点、指定结点为终点的最短路径长度集合。
  • path: Map<String,Map<String,String>> path; 这也是一个二维数组,存储最短路径中,终点的前驱结点编号。

算法思路

  1. 初始化dis和path a)将图的邻接矩阵填入dis中; b)将能够直达的两个结点i和j的path[i][j]设为i,不能直达的设为-1;
  2. 分别以每个结点作为中间结点k,所有结点作为开始结点i,所有结点作为终止结点j,分别判断d[i][k]+d[k][j]是否小于d[i][j];若小于,则: a)d[i][j]=d[i][k]+d[k][j] b)path[i][j]=path[k][j]

代码实现

void Floyd(Map<String,List<ENode>> graph){
    // 初始化
    Map<String, Map<String, Integer>> dis = new HashMap<>();
    Map<String, Map<String, String>> path = new HashMap<>();

    // 对dis和path默认初始化
    for( String start : graph.keySet() ){
        Map<String, Integer> subDis = new HashMap<>();
        Map<String, String> subPath = new HashMap<>();
        for( String end : graph.keySet() ){
            subDis.put( end, Integer.MAX_VALUE );
            subPath.put( end, -1 );
        }
        dis.put( start, subDis );
        path.put( start, subPath );
    }

    // 对dis和path显示初始化
    for( Map.Entry<String, List<ENode>> entry : graph ){
        String start = entry.getKey();
        Map<String, Integer> subDis = dis.get(start);// 二维矩阵dis中的一行
        Map<String, String> subPath = path.get(start);// 二维矩阵path中的一行
        for( ENode edge : entry.getValue() ){
            subDis.put( edge.id, edge.w );
            subPath.put( edge.id, start );
        }
    }

    // 
    for( String k : graph.keySet() ){
        for( String i : graph.keySet() ){
            for( String j : graph.keySet() ){
                if ( dis.get(i).get(k) + dis.get(k).get(j) < dis.get(i).get(j) ) {
                    dis.get(i).put(j, dis.get(i).get(k) + dis.get(k).get(j) );
                    path.get(i).put( j, path.get(k).get(j) );
                }
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Prim算法

普利姆算法,是一种常用的求最小生成树的算法。 最小生成树,使得一个连通图内拥有最小的和。对现实生活中有极大的作用。 主要思路 1 选定一个顶点(与结果无关) 2...

1657
来自专栏desperate633

[编程题] 集合代码

小易最近在数学课上学习到了集合的概念,集合有三个特征:1.确定性 2.互异性 3.无序性.小易的老师给了小易这样一个集合:S = { p/q | w ≤ p ≤...

661
来自专栏大闲人柴毛毛

贪心算法(二)——一般背包问题

题目 有一个背包,最多放M kg的物体(物体大小不限); 有n个物体,每个物体的重量为Wi,每个物体完全放入背包后可获得收益Pi。问:如何放置能获得...

3417
来自专栏Golang语言社区

厚土Go学习笔记 | 29. 接口

在go语言中,接口类型是由一组方法定义的集合。 一个类型是否实现了一个接口,就看这个类型是否实现了接口中定义的所有方法。在go语言中,无需特别的指明定义一个接口...

3455
来自专栏深度学习计算机视觉

计算A+B

代码很冗余 时间限制:1秒空间限制:32768K热度指数:347 **算法知识视频讲解 题目描述 给定两个整数A和B,其表示形式是:从个位开始,每三位数用...

2667
来自专栏Golang语言社区

厚土Go学习笔记 | 29. 接口

在go语言中,接口类型是由一组方法定义的集合。 一个类型是否实现了一个接口,就看这个类型是否实现了接口中定义的所有方法。在go语言中,无需特别的指明? 定义一个...

33110
来自专栏null的专栏

每周算法练习——最近对问题

一、最近对问题的解释     看到算法书上有最近对的问题,简单来讲最近对问题要求出一个包含 ? 个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距...

3376
来自专栏L宝宝聊IT

SQL server 数据库基本插入、删除命令

1866
来自专栏机器学习入门

挑战程序竞赛系列(77):4.3 2-SAT(1)

挑战程序竞赛系列(77):4.3 2-SAT(1) 传送门:POJ 3683: Priest John’s Busiest Day 题意: 有n个婚礼,每个...

1826
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

平均时间O(NlogN),最坏O(N^2) 主要过程四步: 1 如果S中元素为1 或者 0 ,直接返回 2 取S中的任一元素v,称为 枢纽元 3 将集合按照 枢...

18810

扫码关注云+社区