带权图的最短路径算法(Dijkstra)实现

我就是我 2022-03-27 04:48 308阅读 0赞

**一，介绍**

本文实现**带权图**的最短路径算法。给定图中一个顶点，求解该顶点到图中所有其他顶点的最短路径 以及 最短路径的长度。在决定写这篇文章之前，在网上找了很多关于Dijkstra算法实现，但大部分是不带权的。不带权的Dijkstra算法要简单得多（可参考我的另一篇：[无向图的最短路径算法JAVA实现][JAVA]）；而对于带权的Dijkstra算法，最关键的是如何“更新邻接点的权值”。本文采用最小堆作为辅助，**以重新构造堆的方式实现更新邻接点权值。**

对于图而言，存在有向图和无向图。本算法只需要修改一行代码，即可同时实现带权有向图的Dijkstra和带权无向图的Dijkstra。因为，不管图是否是有向的还是无向的，只是构造图的方式不一样而已，而 Dijkstra算法都是一样的。

Dijkstra算法的实现需要一个辅助堆，用来选取当前到源点的距离 最小的那个顶点，这里采用了最小堆来实现。用最小堆保存图中所有顶点到源点的距离，因为Dijkstra算法运行过程中，需要每次选取当前到源点 距离最短 的那个顶点，这步操作用“出堆”很容易实现，但是，当选出该顶点之后， 需要不断地**更新**该顶点的邻接点到源点的距离。而最小堆**不能**很好地支持这种更新操作（关于最小堆[可参考][Link 1]：），这也是为什么《算法导论》中推荐使用菲波拉契堆或者配对堆实现Dijkstra算法的原因。

**二，Dijkstra实现思路**

①初始化，源点的距离初始化为0（源点到它自己的距离当然是0了），源点的前驱顶点为null（因为是从源点开始的嘛，求源点到图中所有其他顶点的minDistance...）。所有其他顶点的前驱顶点也初始化为null，且顶点的“距离”(dist)属性初始化为无穷大(Integer.MAX\_VALUE)，即其他顶点到源点的距离 为无穷大。

②构造堆。将所有的顶点按照“距离”属性(dist) 构造最小堆。显然，由于源点的“距离”属性为0，其他顶点的“距离”属性为Integer.MAX\_VALUE，故最开始构造的堆的 堆顶元素为源点。

③只要堆中还存在元素(while循环)，执行deleteMin从堆中删除堆顶元素，记该元素为v，寻找v的所有邻接点，更新v的所有邻接点的距离。怎么更新的呢？就是比较：❶**v的邻接点**到源点的距离(**dist属性**) ； ❷v到源点的距离(dist属性) **加上** v 到v的邻接点的这条 **边的权值**

v的邻接点的距离(dist属性)取 ❶ ❷ 中较小的那个。

伪代码如下：

DIJKSTRA(G,w,s)
    初始化
    构造堆(Q=V(G))
    while(!isEmpty(Q))
          v=EXTRACT-MIN(Q)
          foreach vertex v_adj  belogns to Adj[v]
                 更新v的邻接点 v_adj

**三，具体代码实现**

在讲解具体实现前，先介绍下如何构造图。假设图中的数据存储在文件中，文件的格式如下：

![715283-20160917145157258-2055443895.png][]

（图的顶点及边信息---暂且用无向图举例）

第一列代表顶点的编号（不用管） ；第二列表示 边的 起始顶点的标识(vertexLabel)

第三列表示 边的 终点的标识；第四列表示边的权值。比如，对于权值为1的那条边而言，它对应的 起始顶点编号为0，对应的结点顶点的编号为1

关于图的解释，可[参考][Link 2]：

这里由于是带权图，故边类(Edge.java)需要有一个权值（边的权值）。

private class Edge{
            private int weight;//边的权值(带权图)
            private Vertex endVertex;
            public Edge(int weight, Vertex endVertex) {
                this.weight = weight;
                this.endVertex = endVertex;
            }

图采用的是邻接表实现，因此每个顶点都会有一个邻接点列表。

1     private class Vertex implements Comparable<Vertex>
     2     {
     3         private String vertexLabel;//顶点标识
     4         private List<Edge> adjEdges;//顶点的所有邻接边(点)
     5         private int dist;//顶点到源点的最短距离
     6         private Vertex preNode;//追溯最短路径
     7         
     8         public Vertex(String vertexLabel){
     9             this.vertexLabel = vertexLabel;
    10             adjEdges = new LinkedList<Edge>();
    11             dist = Integer.MAX_VALUE;
    12             preNode = null;
    13         }
    14 
    15         @Override
    16         public int compareTo(Vertex v) {
    17             if(this.dist >  v.dist)
    18                 return 1;
    19             else if(this.dist < v.dist)
    20                 return -1;
    21             return 0;
    22         }
    23     }

①第4行 adjEdges 是顶点的邻接点列表，表明图采用的是邻接表存储。第5行 dist 表示的是该顶点到源点的最短距离（从而不需要一个单独的距离数组）。第6行preNode 表示该顶点的前驱顶点， 用来记录源点到该顶点路径中经历了哪些顶点。

②Vertex类实现了Comparable接口，因为需要将顶点存储到最小堆中，而最小堆存储的元素需要实现Comparable接口(可以进行顶点的比较)。

最关键的是实现Dijkstra算法中用到的最小堆。关于最小堆的实现，可参考：[数据结构--堆的实现之深入分析][Link 1] 本程序就是用的它。

然后是 dijkstra 的具体实现代码：

1     public void dijkstra(){
     2         BinaryHeap<Vertex> heap = new BinaryHeap<WeightedGraph.Vertex>();
     3         init(heap);//inital heap
     4         
     5         while(!heap.isEmpty())
     6         {
     7             Vertex v = heap.deleteMin();
     8             List<Edge> adjEdges = v.adjEdges;//获取v的所有邻接点
     9             for (Edge e : adjEdges) {
    10                 Vertex adjNode = e.endVertex;
    11                 //update 
    12                 if(adjNode.dist > e.weight + v.dist){
    13                     adjNode.dist = e.weight + v.dist;
    14                     adjNode.preNode = v;
    15                 }
    16             }//end for
    17             
    18             //更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
    19             heap.buildHeap();
    20         }
    21         
    22     }

①第7行，从堆中出一个距离源点路径最短的顶点。刚好符合堆的基本操作（删除堆顶元素），这里也体现了Dijkstra是个贪心算法。

②第8-10行，获取顶点的邻接点

③第12行--15行的if语句，执行更新操作。关于更新操作的具体解释，可参考上面的介绍。

**④由于 ③中的更新操作，破坏了堆序的性质，故需要进行堆调整。但是如何调整呢？由于堆不支持将堆中某个结点的权值降低，故在第19行，直接再次建堆。以保证堆序性质 。但是这里的时间复杂度就大了，故推荐使用更好的数据结构来实现，如Fib堆，因为Fib堆的将某个结点的权值降低是很方便的。**

时间复杂度简要分析如下：buildHeap()的时间复杂度为O(N)，对于图中每个顶点v，出堆时都需要重新构造堆，故最坏情况下时间复杂度为O(V^2)

整个完整代码实现如下：

import java.util.LinkedHashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    
    public class WeightedGraph{
        private class Vertex implements Comparable<Vertex>
        {
            private String vertexLabel;//顶点标识
            private List<Edge> adjEdges;//顶点的所有邻接边(点)
            private int dist;//顶点到源点的最短距离
            private Vertex preNode;//前驱顶点
            
            public Vertex(String vertexLabel){
                this.vertexLabel = vertexLabel;
                adjEdges = new LinkedList<Edge>();
                dist = Integer.MAX_VALUE;
                preNode = null;
            }
    
            @Override
            public int compareTo(Vertex v) {
                if(this.dist >  v.dist)
                    return 1;
                else if(this.dist < v.dist)
                    return -1;
                return 0;
            }
        }
        
        private class Edge{
            private int weight;//边的权值(带权图)
            private Vertex endVertex;
            public Edge(int weight, Vertex endVertex) {
                this.weight = weight;
                this.endVertex = endVertex;
            }
        }
        
        private Map<String, Vertex> weightedGraph;//存储图(各个顶点)
        private Vertex startVertex;//单源最短路径的起始顶点
        
        
        //图的信息保存在文件中,从文件中读取成字符串graphContent
        public WeightedGraph(String graphContent) {
            weightedGraph = new LinkedHashMap<String, WeightedGraph.Vertex>();
            buildGraph(graphContent);//解析字符串构造图
        }
        private void buildGraph(String graphContent){
            String[] lines = graphContent.split("\n");
            
            String startNodeLabel, endNodeLabel;
            Vertex startNode, endNode;
            int weight;
            for(int i = 0; i < lines.length; i++){
                String[] nodesInfo = lines[i].split(",");
                startNodeLabel = nodesInfo[1];
                endNodeLabel = nodesInfo[2];
                weight = Integer.valueOf(nodesInfo[3]);
                
                endNode = weightedGraph.get(endNodeLabel);
                if(endNode == null){
                    endNode = new Vertex(endNodeLabel);
                    weightedGraph.put(endNodeLabel, endNode);
                }
                
                startNode = weightedGraph.get(startNodeLabel);
                if(startNode == null){
                    startNode = new Vertex(startNodeLabel);
                    weightedGraph.put(startNodeLabel, startNode);
                }
                Edge e = new Edge(weight, endNode);
                //对于无向图而言,起点和终点都要添加边
    //            endNode.adjEdges.add(e);
                startNode.adjEdges.add(e);
            }
            startVertex = weightedGraph.get(lines[0].split(",")[1]);//总是以文件中第一行第二列的那个标识顶点作为源点
        }
        
    
        public void dijkstra(){
            BinaryHeap<Vertex> heap = new BinaryHeap<WeightedGraph.Vertex>();
            init(heap);//inital heap
            
            while(!heap.isEmpty())
            {
                Vertex v = heap.deleteMin();
                List<Edge> adjEdges = v.adjEdges;//获取v的所有邻接点
                for (Edge e : adjEdges) {
                    Vertex adjNode = e.endVertex;
                    //update 
                    if(adjNode.dist > e.weight + v.dist){
                        adjNode.dist = e.weight + v.dist;
                        adjNode.preNode = v;
                    }
                }//end for
                
                //更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
                heap.buildHeap();
            }
            
        }
        private void init(BinaryHeap<Vertex> heap){
            startVertex.dist = 0;//源点到其自身的距离为0
            for (Vertex v : weightedGraph.values()) {
                heap.insert(v);
            }
        }
        
        public void showDistance(){
            for (Vertex v : weightedGraph.values()) {
                printPath(v);
                System.out.println();
                System.out.println("顶点 " + v.vertexLabel + "到源点"  + startVertex.vertexLabel + " 的距离: " + v.dist);
            }
        }
        
        //打印源点到 end 顶点的 最短路径
        private void printPath(Vertex end)
        {
            if(end.preNode != null)
                printPath(end.preNode);
            System.out.print(end.vertexLabel + "--> ");
        }
    }

buildGraph()方法中：如果是有向图，只需要起点添加边；如果是无向图，则起点和终点都需要添加边。但不管是有向图还是无向图Dijkstra算法都一样。

Edge e = new Edge(weight, endNode);
                //对于无向图而言,起点和终点都要添加边
    //            endNode.adjEdges.add(e);
                startNode.adjEdges.add(e);

关于如何测试WeightedGraph.java，需要构造一个图。构造图：可参考[有向图的拓扑排序算法JAVA实现][Link 2] 中的“完整代码实现”中的FileUtil.java 和 TestXXX.java

public class TestDijkstra {
        public static void main(String[] args) {
               String graphFilePath;
                if(args.length == 0)
                    graphFilePath = "F:\\graph2.txt";
                else
                    graphFilePath = args[0];
                
                String graphContent = FileUtil.read(graphFilePath, null);
                WeightedGraph graph = new WeightedGraph(graphContent);
                graph.dijkstra();
                
                graph.showDistance();
        }
    }

[JAVA]: http://www.cnblogs.com/hapjin/p/5435724.html
[Link 1]: http://www.cnblogs.com/hapjin/p/5459991.html
[715283-20160917145157258-2055443895.png]: /images/20220327/27f1db518c5b4f9c8eb195ce65c8b650.png
[Link 2]: http://www.cnblogs.com/hapjin/p/5432996.html