贪心算法(五)——迪杰斯特拉算法

问题描述

给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。

数据结构

  • dis: Map<String,Integer> dis; 存储原点s到指定节点的最短路径长度。 key表示节点编号,value表示s到该终止节点的最短路径长度。
  • path: Map<String,String> path; 存储以指定结点为终点的最短路径中,该终点的上一个结点的编号。 key表示终点编号,value表示终点的前驱结点编号。
  • S集合 和 V集合 将所有的结点分成两个集合:
    1. S集合中存储已经计算出最短路径的结点;
    2. V集合中存储尚未计算出最短路径的结点。
  • k结点: 最新选入S集合的结点,即刚刚计算出最短路径的结点。
  • mark: Map<String,Boolean> mark; 用于标识指定结点是否已被选入S集合(即是否已经计算出最短路径)。 key为结点编号,value为是否属于S集合。

算法步骤

  1. 初始化 a)初始化mark:将初始节点s选入S集合; b)初始化dis:将与s结点所有出边的权值写入dis中; c)初始化path:将所有与s结点直接关联的终止结点的path值设为s;
  2. 遍历dis,找出最短的边,将该边的终点设为k,并纳入S集合中;
  3. 遍历k的所有出边,并更新dis和path(设与k直接关联的所有结点为j): 若d[k]+w< k,j> 小于 d[j],则: a)d[j]=d[k]+w< k,j> b)path[j]=k;
  4. 重复步骤2、3,n-2次后停止。(n为结点数量)

示例

代码实现

/**
 * 迪杰斯特拉算法
 * @ graph:图的邻接表
 * @ start:起始结点
 */
void Dijkstra(Map<String,List<ENode>> graph, String start){
    // 初始化
    Map<String,Integer> dis = new HashMap<>();
    Map<String,String> path = new HashMap<>();
    Map<String,Boolean> mark = new HashMap<>();
    String k = start;

    for( String id : graph.keySet ){
        dis.put( id, Integer.MAX_VALUE );
        path.put( id, null );
        mark.put( id, false );
    }

    for( ENode edge : graph.get(start) ){
        dis.put( edge.id, edge.w );
        path.put( edge.id, start );
    }
    mark.put( k, true );

    int n = graph.keySet().size();// 图中结点个数
    // 进行n-2次扫描,每次选一个结点放入S集合
    for( int i=1; i<=n-2; i++ ){
        k = selectKfromDis(dis,mark);// 从dis中选尚未访问的最小值作为k
        mark.put( k, true );
        for( ENode edge : graph.get(k) ){
            if ( !mark.get(edge.id) && dis.get(k)+edge.w < dis.get(edge.id) ) {
                dis.put( edge.id, dis.get(k)+edge.w );
                path.put( edge.id, k );
            }
        }
    }
}

/**
 * 从dis中选一条尚未访问过的最短的边
 */
String selectKfromDis( Map<String,Integer> dis, Map<String, Boolean> mark ){
    int min = Integer.MAX_VALUE;
    String id = null;
    for( Map.Entry<String,Integer> entry : dis ){
        if ( !mark.get(entry.getKey()) && entry.getValue() < min ) {
            min = entry.getValue();
            id = entry.getKey();
        }
    }
    return id;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

213100
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(下)

上面两篇我们了解了树的基本概念以及二叉树的遍历算法,还对二叉查找树进行了模拟实现。数学表达式求值是程序设计语言编译中的一个基本问题,表达式求值是栈应用的一个典型...

11220
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

9710
来自专栏TechBox

数据结构与算法之线性表前言线性表

20150
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

15810
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

42870
来自专栏腾讯IVWEB团队的专栏

ES6 中的 Set

ES6 新增了几种集合类型,本文主要介绍Set以及其使用。Set对象是值的集合,你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次,即 Set 中的...

85500
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

32050
来自专栏Android机动车

数据结构学习笔记——线性表(中)

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的...

9830
来自专栏haifeiWu与他朋友们的专栏

聊聊HashSet源码

今天聊一下HashSet源码,HashSet内部基本使用HashMap来实现,本博客将通过一下几个方向讲解。

9730

扫码关注云+社区

领取腾讯云代金券