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

问题描述

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

数据结构

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

相关文章

来自专栏desperate633

LintCode 最小路径和题目分析代码

给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径。

482
来自专栏小樱的经验随笔

Codeforces 626A Robot Sequence(模拟)

A. Robot Sequence time limit per test:2 seconds memory limit per test:256 megaby...

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

后缀自动机经典操作

1394
来自专栏Python小白进阶之旅

Python基本的排序算法比较,sorted的实现方法

简介:依次检查需要排序的列表,每次取出一个元素放入另一个排好序的列表中的适当位置。

693
来自专栏Coding迪斯尼

在未知长度的超大数组中线性时间内查找第k大的元素

给定一个长度为n的数组,n是一个很大的值,而且事先不知道n的大小,给定一个确定的数值k,要求设计一个找出数组中第k大的元素,要求算法需要的空间不能超过O(k)。

782
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(7) - 简单排序总结

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

3149 爱改名的小融 2

3149 爱改名的小融 2 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description W...

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

洛谷P3374 【模板】树状数组 1(CDQ分治)

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个整数N、M,分...

3175
来自专栏算法channel

面试必备|单链表反转思路图形解析

01 — 单链表 链表玩的是指针操作,非常容易出错,尽管看似很简单。 先定义一种单链表,JAVA(或C#)描述的数据结构如下: public class...

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

P1062 数列

题目描述 给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是: 1,3,4,9,...

2647

扫描关注云+社区