频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
Dijkstra 算法用优先队列的java实现
2017-04-10 09:26:00           
收藏   我要投稿

Dijkstra 算法用优先队列的java实现:dijkstra这个算法的意思百度下大概就能明白。我主要讲的是如何实现。
首先,我们如何用java去保存一张有向图?
我用hashmap去存它的起点位置,然后value用list加节点的方式,感觉就像链表一样。去存储
地图模板

//创建地图
/*
 * S——16——>C—— 2——>D
 * | \     ^ ^     ^
 * 4  8    |  \    |
 * |    \  7   5   6
 * v     v |    \  |
 * A—— 3——>B—— 1——>E
 */
class Graph
{
    Map> map=new HashMap>();//输出的地图
    Graph()
    {
        List list=new ArrayList();
        list.add(new Node('S','A',4));
        list.add(new Node('S','B',8));
        list.add(new Node('S','C',16));
        list.add(new Node('A','B',3));
        list.add(new Node('B','C',7));
        list.add(new Node('B','E',1));
        list.add(new Node('C','D',2));
        list.add(new Node('E','C',5));
        list.add(new Node('E','D',6));

        for(int i=0;i temp=map.get(list.get(i).getSrc());
            if(temp==null)
                temp=new ArrayList();
            temp.add(list.get(i));
            map.put(list.get(i).getSrc(), temp);
        }
    }
}

class Node
{
    private Character src;//起点
    private Character des;//终点
    private int len;      //距离长度
    private int path=Integer.MAX_VALUE;//初始设置为无穷长
    boolean die=false;    //访问过一次后就死亡
    Node(){}
    Node(Character src,Character des,int len)
    {
        this.src=src;
        this.des=des;
        this.len=len;
    }
    void setPath(int path)
    {
        this.path=path;
    }
    int getPath()
    {
        return path;
    }
    Character getSrc()
    {
        return src;
    }
    Character getDes()
    {
        return des;
    }
    int getLen()
    {
        return len;
    }
}

然后为了凸显出链表的效率。我们先来个普通模式的dijkstra算法的实现,这个方式去实现其算法复杂度是O(V^2)V是节点数量

public class Dijkstra 
{  
    public static Map dijkstra(Map> map,Character c)
    {
        Queue heap=new LinkedList();

        //初始节点
        Node root=new Node(c,c,0);
        root.setPath(0);
        heap.add(root);

        Map result=new HashMap();
        while(!heap.isEmpty())
        {
            Node x=heap.poll(),y = null;
            List temp=map.get(x.getDes());
            if(temp==null)
                continue;
            for(int i=0;ix.getPath()+y.getLen())
                {
                    temp.get(i).setPath(x.getPath()+y.getLen());
                    if(temp.get(i).die==false)
                    {
                        heap.add(temp.get(i)); 
                        temp.get(i).die=true;
                    }
                    if(result.get(temp.get(i).getDes())==null)
                    {
                        result.put(temp.get(i).getDes(),temp.get(i).getPath());
                    }
                    if(result.get(temp.get(i).getDes())>temp.get(i).getPath())
                    {
                        result.put(temp.get(i).getDes(),temp.get(i).getPath());
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] argc)
    {
        Graph graph=new Graph();
        Map result=dijkstra(graph.map,'S');
        for(Map.Entry entry:result.entrySet())
        {
            System.out.println("S-->"+entry.getKey()+" 长度"+entry.getValue());
        }
    }
}

这里写图片描述

大致就是这样实现下。
然后我们就要讨论为什么要用有限队列?因为它是堆的形式。堆便于取出最值,如果一个算法中需要多次取最大或者最小值,那么堆就是个最好的存放容器,其建堆只要O(N)的时间,增删,堆化时间复杂度也只要O(logn)。有很大的优势。

用堆去存储 复杂度降低到O(VlogV)
代码如下<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwcmUgY2xhc3M9"brush:java;"> import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.PriorityQueue; //创建地图 /* * S——16——>C—— 2——>D * | \ ^ ^ ^ * 4 8 | \ | * | \ 7 5 6 * v v | \ | * A—— 3——>B—— 1——>E */ class Graph { Map> map=new HashMap>();//输出的地图 Graph() { List list=new ArrayList(); list.add(new Node('S','A',4)); list.add(new Node('S','B',8)); list.add(new Node('S','C',16)); list.add(new Node('A','B',3)); list.add(new Node('B','C',7)); list.add(new Node('B','E',1)); list.add(new Node('C','D',2)); list.add(new Node('E','C',5)); list.add(new Node('E','D',6)); for(int i=0;i temp=map.get(list.get(i).getSrc()); if(temp==null) temp=new ArrayList(); temp.add(list.get(i)); map.put(list.get(i).getSrc(), temp); } } } class Node { private Character src;//起点 private Character des;//终点 private int len; //距离长度 Node(){} Node(Character src,Character des,int len) { this.src=src; this.des=des; this.len=len; } Character getSrc() { return src; } Character getDes() { return des; } int getLen() { return len; } } public class Dijkstra2 { static Map dijkstra(Map> graph,Character source) { //堆的初始化 PriorityQueue> queue=new PriorityQueue>((a,b)->a.getValue()-b.getValue()); Map map=new HashMap(); map.put(source, 0); queue.add(map.entrySet().iterator().next()); Map visited=new HashMap(); while(!queue.isEmpty()) { //从堆中获取最小距离的节点 Entry temp=queue.poll(); //讲距离值添加到visited if(visited.get(temp.getKey())==null) visited.put(temp.getKey(), temp.getValue()); if(graph.get(temp.getKey())==null) { continue; } //更新与temp相邻各节点neighbour的distance for(int i=0; i temp2=new HashMap(); temp2.put(graph.get(temp.getKey()).get(i).getDes(), temp.getValue()+graph.get(temp.getKey()).get(i).getLen()); queue.add(temp2.entrySet().iterator().next()); } } return visited; } public static void main(String[] argc) { Graph graph=new Graph(); Map result=dijkstra(graph.map,'S'); for(Map.Entry entry:result.entrySet()) { System.out.println("S-->"+entry.getKey()+" 长度"+entry.getValue()); } } }

这里写图片描述

点击复制链接 与好友分享!回本站首页
上一篇:利用UDP实现用户聊天程序
下一篇:java 实现构造最大堆
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站