最短路径算法

亦凉 2023-06-23 03:00 163阅读 0赞

到底是贪心还是动态规划？  
Dijkstra算法  
抽象问题，选择合适的数据结构抽象问题  权重图，本质求两节点最小权重值  
从起点开始遍历所有的临接节点，将节点权重维护到最小堆中  
每次以最小堆对应的顶点为起点再次遍历临接节点：  
0) 默认到最小节点的距离都是MAX INT，用数组存储，index顶点值  
1）将节点标记为已遍历，所有临接节点距离与当前数组中距离比较：  
2）如果大于当前距离不处理，否则入队并更新数组，未入最小堆进行入堆标记，  
结束条件:最小堆对应的节点就是目的节点

A\*算法  
如果图非常大，那么Dijkstra算法就会十分耗时，A\*算法就是对其的改造，是为了快速找出一条接近于最短路线的次优路线。

主要是为了避免开始的远方绕路行为  
Dijkstra 判断出堆的点：距离到起点最近的顶点  
A\*:g(i)+h(i)来判断最先出堆的点,g(i):顶点起始点的距离，h(i):顶点到终点的距离，如果和最小，说明总的距离可能最小。

public class Dijkstra {
        public static void main(String[] args) {
    
            LinkedList<Edege>[] list = new LinkedList[4];
            LinkedList<Edege> list1 = new LinkedList();
            Edege e1 =new Edege(1,2,3);
            list1.add(e1);
            Edege e2 =new Edege(1,3,10);
            list1.add(e2);
    
            LinkedList<Edege> list2 = new LinkedList();
            LinkedList<Edege> list3 = new LinkedList();
            Edege e3 =new Edege(2,3,4);
            list2.add(e3);
    
            list[1] = list1;
            list[2] = list2;
            list[3] = list3;
    
            Graphic g = new Graphic(3,list);
            System.out.println(getShortedRoad(g,1,3));;
    
    //        PriorityQueue queue = new PriorityQueue(3);
    //        Verte a1 = new Verte(1,3);
    //        Verte a2 = new Verte(2,2);
    //        Verte a3 = new Verte(3,1);
    //        queue.add(a1);
    //        queue.add(a2);
    //        queue.add(a3);
    //        a2 = new Verte(2,-1);
    //        queue.update(a2);
    //        System.out.println();
        }
    
    
    
        public static  int getShortedRoad(Graphic g, int start, int end){
            if(start == end){
                return 0;
            }
    
            LinkedList<Edege>[] list = g.getList();
            int nodeNum = g.getV();
    
            // index：图的顶点 value：start到该顶点的最小距离
            int[] roadlength = new int[nodeNum+1];
            for(int i =0; i<nodeNum+1; i++){
                roadlength[i] = Integer.MAX_VALUE;
            }
    
            boolean[] visited = new boolean[nodeNum+1];
            boolean[] inqueue = new boolean[nodeNum+1];
    
            PriorityQueue roadDui  = new PriorityQueue(nodeNum+1);
            Verte v = new Verte(1,0);
            roadDui.add(v);
            inqueue[v.getId()] =  true;
    
            while(!roadDui.isEmpty()){
                Verte  temp = roadDui.poll();
                roadlength[temp.getId()] = temp.getDist();
                if(temp.getId() == end ){
                    return temp.getDist();
                }
                if(visited[temp.getId()] == false){
                    visited[temp.getId()] = true;
                    LinkedList<Edege> edeges = list[temp.getId()];
                    if(null != edeges){
                        for(int i=0; i<edeges.size(); i++){
                            Verte v1 = new Verte(edeges.get(i).getTid(), edeges.get(i).getW() + temp.getDist());
                            if(v1.getDist() < roadlength[v1.getId()]){
                                roadlength[v1.getId()] = v1.getDist();
                            }else{
                                v1.setDist(roadlength[v1.getId()]);
                            }
                            if(inqueue[v1.getId()] == true ){
                                roadDui.update(v1);
                            }else{
                                roadDui.add(v1);
                                inqueue[v1.getId()] = true;
                            }
                        }
                    }
    
                }
            }
            return -1;
        }
    
        // 下面这个类是为了dijkstra实现用的
        private static  class Verte {
            public int id; // 顶点编号ID
            public int dist; // 从起始顶点到这个顶点的距离
            public Verte(int id, int dist) {
                this.id = id;
                this.dist = dist;
            }
    
            public int getId() {
                return id;
            }
    
            public void setId(int id) {
                this.id = id;
            }
    
            public int getDist() {
                return dist;
            }
    
            public void setDist(int dist) {
                this.dist = dist;
            }
        }
    
        // 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
        private static  class PriorityQueue { // 根据vertex.dist构建小顶堆
            private Verte[] nodes;
            private int count;
            public PriorityQueue(int v) {
                this.nodes = new Verte[v+1];
                this.count = v;
            }
            public Verte poll() {
                Verte v = nodes[1];
                nodes[1] = null;
                int i =1;
                while(2*i<count && (nodes[2*i] != null || nodes[2*1+1] != null)){
                    if(nodes[2*i] != null && nodes[2*i+1] != null){
                        // 左右节点均不为空
                        if(nodes[2*i].getDist() < nodes[2*i+1].getDist() ){
                            nodes[i] = nodes[2*i];
                            nodes[2*i] = null;
                            i = 2*1;
                        }else{
                            // 右节点不为空
                            nodes[i] = nodes[2*i+1];
                            nodes[2*i+1] = null;
                             i = 2*1+1;
                        }
                    }else if(nodes[2*i] != null){
                        // 左节点不为空
                        nodes[i] = nodes[2*i];
                        nodes[2*i] = null;
                        i = 2*1;
                    }else{
                        // 右节点不为空
                        nodes[i] = nodes[2*i+1];
                        nodes[2*i+1] = null;
                        i = 2*1+1;
                    }
                }
                return v;
            }
    
            public void add(Verte vertex) {
                int index  = 1;
                for(int i=1; i<=count; i++){
                    if(nodes[i]==null){
                        nodes[i]=vertex;
                        index = i;
                        break;
                    }
                }
                int i =index;
                while( i != 1 && nodes[i].getDist() < nodes[i/2].getDist()){
                    Verte temp = nodes[i/2];
                    nodes[i/2] = nodes[i];
                    nodes[i] = temp;
                    i = i/2;
                }
            }
    
            // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
            public void update(Verte vertex) {
                int index = 0;
                for(int i = 1; i<=count; i++){
                    if(null != nodes[i] && nodes[i].getId() == vertex.getId()){
                        nodes[i] = vertex;
                        index = i ;
                        break;
                    }
                }
                if(index == 0 ){
                    return;
                }
                int left = index*2;
                int right = index*2+1;
    
                while(left<=count && (nodes[left] != null || nodes[right] != null)){
                    if(nodes[left] != null && nodes[index].getDist() > nodes[left].getDist()  ){
                        Verte temp = nodes[left];
                        nodes[left] = nodes[index];
                        nodes[index] = temp;
                        index = left;
                    }else if(nodes[right] != null && nodes[index].getDist() > nodes[right].getDist()  ){
                        Verte temp = nodes[right];
                        nodes[right] = nodes[index];
                        nodes[index] = temp;
                        index = right;
                    }else{
                        break;
                    }
                    left = index*2;
                    right = index*2+1;
                }
    
                int parent  = index/2;
                while(parent != 0 && nodes[parent].getDist() > nodes[index].getDist()){
                    Verte temp = nodes[parent];
                    nodes[parent] = nodes[index];
                    nodes[index] = temp;
                    index = parent;
                    parent  = index/2;
                }
            }
            public boolean isEmpty() {
                return nodes[1] == null;
            }
    
        }
    
    
        static class Graphic{
            int v;
            LinkedList<Edege>[] list ;
            public Graphic(int v, LinkedList<Edege>[] list){
                this.v = v;
                this.list = list;
            }
    
            public int getV() {
                return v;
            }
    
            public void setV(int v) {
                this.v = v;
            }
    
            public LinkedList<Edege>[] getList() {
                return list;
            }
    
            public void setList(LinkedList<Edege>[] list) {
                this.list = list;
            }
        }
    
        static class Edege{
            public int sid;
            public int tid;
            public int w;
    
            public Edege(int sid, int tid, int w){
                this.sid = sid;
                this.tid = tid;
                this.w = w;
            }
    
            public int getSid() {
                return sid;
            }
    
            public void setSid(int sid) {
                this.sid = sid;
            }
    
            public int getTid() {
                return tid;
            }
    
            public void setTid(int tid) {
                this.tid = tid;
            }
    
            public int getW() {
                return w;
            }
    
            public void setW(int w) {
                this.w = w;
            }
        }
    }