专栏首页大闲人柴毛毛动态规划法(二)——弗洛伊德算法

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

问题描述

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

迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉算法即可求的任意两结点间的最短路径。迪杰斯特拉算法的时间复杂度为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 条评论
登录 后参与评论

相关文章

  • Java8新特性——StreamAPI(二)

    1. 收集器简介 收集器用来将经过筛选、映射的流进行最后的整理,可以使得最后的结果以不同的形式展现。 collect方法即为收集器,它接收Collector接...

    大闲人柴毛毛
  • 剑指offer代码解析——面试题16反转单链表

    本题的详细解析均在代码中注释: /** * 题目:将单链表反转,并输出反转后链表的头结点 * @author 大闲人柴毛毛 */ public class...

    大闲人柴毛毛
  • 剑指offer代码解析——面试题25二叉树中和为某一值的路径

    题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

    大闲人柴毛毛
  • Spring Boot Debug调试

    在使用maven插件执行spring-boot:run进行启动的时候,如果设置的断点进不去,要进行以下的设置。 1、添加jvm参数配置 在spring-boot...

    Java技术栈
  • 快递查询接口API/插件开发使用

      快递接口/插件是电商网站和系统商用来实现查询快递功能的主要方法,就类似淘宝京东查询物流轨迹一样,嵌入到自己系统里。

    用户6827397
  • 0754-5.16.2-Hive中使用Substr拆分含中文乱码字符串报错异常分析

    从上游Oracle数据库中导出的携带中文乱码且编码集为ISO-8859-1的数据文件,将导出的数据文件导入到Hive表,在原始表的基础上通过创建视图,按照与上游...

    Fayson
  • PHPUnit 详解

    本文介绍了 PHP 单元测试框架 PHPUnit。 官方网站:https://phpunit.de/ GitHub:https://github.com/seb...

    康怀帅
  • 架构设计基础知识整理

    From http://msdn.microsoft.com/en-us/library/ff647859.aspx

    哲洛不闹
  • Web服务器与客户端三种http交互方式

    近期在对接项目时用到http方式与第三方交互数据,由于中间沟通不足导致走了不少弯路,至此特意花了点时间总结服务端与客户端数据交互的方式,本地搭建两个项目一个作为...

    Jack Chen
  • J2SE1.5的新特点(之一)

    J2SE1.5的新特点<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:off...

    田春峰-JCJC错别字检测

扫码关注云+社区

领取腾讯云代金券