【数据结构与算法】【算法思想】Dijkstra算法

﹏ヽ暗。殇╰゛Y 2022-12-10 03:44 210阅读 0赞

图的两种搜索算法，深度优先搜素和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图，也就是图中的每条边都有一个权重，该如何计算两点之间的最短路径？最短路径算法（Shortest Path Algorithm）。

一：算法解析  
最优问题包含三个：最短路线，最少用时，最少红绿灯。  
1，解诀软件开发中的实际问题，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。  
2，图的表达能力强，可以将求解的最短路径问题转化为：在一个有向有权图中，求两个顶点间的最短路径。  
3，要解决这个问题，有个非常经典的算法，最短路径算法，更准确的叫：单源最短路径算法（一个顶点到一个顶点）。提到最短路径算法，最出名的莫过于DijKstra算法。

### Dijkstra算法 ###

#### 算法结构 ####

public class Graph {  // 有向有权图的邻接表表示
      private LinkedList<Edge> adj[]; // 邻接表
      private int v; // 顶点个数
    
      public Graph(int v) { 
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) { 
          this.adj[i] = new LinkedList<>();
        }
      }
    
      public void addEdge(int s, int t, int w) {  // 添加一条边
        this.adj[s].add(new Edge(s, t, w));
      }
    
      private class Edge { 
        public int sid; // 边的起始顶点编号
        public int tid; // 边的终止顶点编号
        public int w; // 权重
        public Edge(int sid, int tid, int w) { 
          this.sid = sid;
          this.tid = tid;
          this.w = w;
        }
      }
      // 下面这个类是为了dijkstra实现用的
      private class Vertex { 
        public int id; // 顶点编号ID
        public int dist; // 从起始顶点到这个顶点的距离
        public Vertex(int id, int dist) { 
          this.id = id;
          this.dist = dist;
        }
      }
    }

#### 实现算法 ####

// 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
    private class PriorityQueue {  // 根据vertex.dist构建小顶堆
      private Vertex[] nodes;
      private int count;
      public PriorityQueue(int v) { 
        this.nodes = new Vertex[v+1];
        this.count = v;
      }
      public Vertex poll() {  // TODO: 留给读者实现... }
      public void add(Vertex vertex) {  // TODO: 留给读者实现...}
      // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
      public void update(Vertex vertex) {  // TODO: 留给读者实现...} 
      public boolean isEmpty() {  // TODO: 留给读者实现...}
    }
    
    public void dijkstra(int s, int t) {  // 从顶点s到顶点t的最短路径
      int[] predecessor = new int[this.v]; // 用来还原最短路径
      Vertex[] vertexes = new Vertex[this.v];
      for (int i = 0; i < this.v; ++i) { 
        vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
      }
      PriorityQueue queue = new PriorityQueue(this.v);// 小顶堆
      boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
      vertexes[s].dist = 0;
      queue.add(vertexes[s]);
      inqueue[s] = true;
      while (!queue.isEmpty()) { 
        Vertex minVertex= queue.poll(); // 取堆顶元素并删除
        if (minVertex.id == t) break; // 最短路径产生了
        for (int i = 0; i < adj[minVertex.id].size(); ++i) { 
          Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
          Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
          if (minVertex.dist + e.w < nextVertex.dist) {  // 更新next的dist
            nextVertex.dist = minVertex.dist + e.w;
            predecessor[nextVertex.id] = minVertex.id;
            if (inqueue[nextVertex.id] == true) { 
              queue.update(nextVertex); // 更新队列中的dist值
            } else { 
              queue.add(nextVertex);
              inqueue[nextVertex.id] = true;
            }
          }
        }
      }
      // 输出最短路径
      System.out.print(s);
      print(s, t, predecessor);
    }
    
    private void print(int s, int t, int[] predecessor) { 
      if (s == t) return;
      print(s, predecessor[t], predecessor);
      System.out.print("->" + t);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]  
用 vertexes 数组，记录从起始顶点到每个顶点的距离（dist）。起初，我们把所有顶点的 dist 都初始化为**无穷大**（也就是代码中的Integer.MAX\_VALUE）。  
把起始顶点的 dist 值初始化为 0，然后将其放到优先级队列中。我们从优先级队列中取出 dist 最小的顶点 minVertex，然后考察这个顶点可达的所有顶点（代码中的 nextVertex）。如果 minVertex 的 dist 值加上 minVertex 与 nextVertex 之间边的权重 w 小于 nextVertex 当前的 dist 值，也就是说，存在另一条更短的路径，它经过 minVertex 到达 nextVertex。那我们就把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w。然后，我们把 nextVertex 加入到优先级队列中。重复这个过程，直到找到终止顶点 t 或者队列为空。  
以上就是 Dijkstra 算法的核心逻辑。除此之外，代码中还有两个额外的变量，**predecessor 数组和 inqueue 数组**。  
predecessor 数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。最后，我们通过递归的方式，将这个路径打印出来。打印路径的 print 递归代码我就不详细讲了，这个跟我们在图的搜索中讲的打印路径方法一样。如果不理解的话，你可以回过头去看下那一节。  
inqueue 数组是为了避免将一个顶点多次添加到优先级队列中。我们更新了某个顶点的 dist 值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。

#### Dijkstra算法的时间复杂度 ####

O(E\*log V)，E表示边的个数，V表示元素个数不会超过顶点的个数  
5,Dijkstra最短路径算法，实际上最短路径算法还有很多，比如Bellford算法，Floyd算法等。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/9cbe48c6929d4d989f892276c3a5efc2.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png