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

问题描述

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

数据结构

  • 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 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

2916
来自专栏武培轩的专栏

剑指Offer-整数中1出现的次数(从1到n整数中1出现的次数)

package Other; /** * 整数中1出现的次数(从1到n整数中1出现的次数) * 求出1~13的整数中1出现的次数,并算出100~1300的...

2843
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

534
来自专栏机器学习算法全栈工程师

归并排序

作者:柳行刚 编辑:徐 松 基本思想 归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使...

35210
来自专栏一枝花算不算浪漫

HashMap中的resize以及死链的情况

35912
来自专栏小勇DW3

HashMap 与 ConcrrentHashMap 使用以及源码原理分析

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为...

1473
来自专栏我是攻城师

理解Java8并发工具类ConcurrentHashMap的实现

前面的文章已经分析过List和Queue相关的接口与并发实现类,本篇我们来分析一下非常Java里面非常重要的一个数据结构HashMap。(注意Set类型在这里我...

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

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

2206
来自专栏和蔼的张星的图像处理专栏

算法1.排序二分查找及其变种

这个我也不知道能写多少,只是最近快放假了实在懒得看DSP了,而且卡在一个地方了,什么都不干又感觉心慌的很,所以又回头看看算法的东西。一些测试程序放在这里

782
来自专栏恰同学骚年

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

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

711

扫码关注云+社区