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

问题描述

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

数据结构

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

相关文章

扫码关注云+社区