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

问题描述

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

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

相关文章

来自专栏butterfly100

HashMap源码阅读

HashMap是Map家族中使用频度最高的一个,下文主要结合源码来讲解HashMap的工作原理。 1. 数据结构 HashMap的数据结构主要由数组+链表+红黑...

34790
来自专栏desperate633

LintCode 数字组合 II题目代码

给出一组候选数字(C)和目标数字(T),找出C中所有的组合,使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

5720
来自专栏机器学习与自然语言处理

04-树5. File Transfer--并查集

  对于一个集合常见的操作有:判断一个元素是否属于一个集合;合并两个集合等等。而并查集是处理一些不相交集合(Disjoint Sets)的合并及查询问题的有利工...

20450
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

29160
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

8100
来自专栏小二的折腾日记

牛客网-剑指offer-2

二叉树是觉得很烦的东西了,比链表复杂很多,看着头都有点疼啊,但是没办法,生活就是这样,只有把不会的会了才会进步,怕的变得不怕才能越来越厉害。 常规的理解一下:二...

35720
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

14220
来自专栏开源优测

[快学Python3]数据结构与算法-二分查找

概述 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。 其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁...

32850
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

33750
来自专栏GIS讲堂

geotools中等值面的生成与OL3中的展示

本文讲述如何在geotools中IDW插值生成等值面,并根据给定shp进行裁剪,并生成geojson数据,以及Openlayers3中展示。

27650

扫码关注云+社区

领取腾讯云代金券