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

问题描述

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

数据结构

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

相关文章

来自专栏有趣的Python

7-玩转数据结构-集合与映射

上一章我们详细的介绍了二分搜索树的底层实现。这章我们介绍两个高层的数据结构,集合和映射。这种高层的数据结构,更像是我们定义好了使用接口规则,但是具体的底层实现可...

2151
来自专栏我是业余自学C/C++的

用vector描述线性表

1333
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

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

聊聊HashSet源码

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

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

Leetcode 209 Minimum Size Subarray Sum

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

19910
来自专栏用户画像

7.7.5 最佳归并树

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

661
来自专栏JavaEdge

Java中Collections.sort()方法的演变结果分析源码分析关于Java8中Collections.sort方法的修改

3717
来自专栏Android机动车

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

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

843
来自专栏用户3030674的专栏

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

1201
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

883

扫码关注云+社区