• 单源最短路径算法，用于计算一个节点到其他所有节点的最短路径
    • 特点：以起始点为中心向外层层扩展，直到扩展到终点为止
    • 核心思想：贪心算法
    • 前提条件：图中不存在负权边
    • 问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径（单源最短路径）
    • 算法描述
      • 从选定点开始抛入优先队列（路径一般为 0），boolean 数组标记 0 的位置（最短为 0），0 周围连通的点抛入优先队列中，并把各点距离记录到对应数组内（如果小于就更新，大于就不动，初始第一次是无穷肯定会更新），第一次结束
      • 从队列中抛出距离最近的点 B（第一次是 0 周围邻居），标记这个点为 true，并将这个点的邻居加入队列（下一次确定的最短点在前面未确定和这个点邻居中产生），更新通过 B 点计算各个位置的长度，小于则更新

    Dijkstra算法1.png

    • 重复 2 操作，直到所有点确定

    Dijkstra算法2.png

    • 实现

      1. public class dijkstra {
      2.  static class node{
      3.      int x;        //节点编号
      4.      int length;    //长度
      6.      public node(int x,int lenth){
      7.          this.x = x;
      8.          this.length = length;
      9.      }
      10.  }
      12.  public static void main(String[] args) {
      13.      int[][] map = new int[6][6];        //记录权值，顺便记录链接情况，可以考虑附加邻接表
      14.      initmap(map);                        //初始化
      15.      boolean bool[] = new boolean[6];    //判断是否已经确定
      16.      int len[] = new int[6];                //长度
      18.      for(int i=0;i<6;i++){
      19.          len[i] = Integer.MAX_VALUE;
      20.      }
      22.      Queue<node> q1 = new PriorityQueue<node>(com);
      23.      len[0] = 0;                            //从0这个点开始
      24.      q1.add(new node(0,0));
      25.      int count = 0;                        //计算执行了几次dijkstra
      26.      while(!q1.isEmpty()) {
      27.          node t1 = q1.poll();
      28.          int index = t1.x;                //节点编号
      29.          int length = t1.length;            //节点当前点距离
      30.          bool[index] = true;                //抛出的点确定
      31.          count++;                        //执行6次就可确定不需继续执行
      32.          for(int i=0;i<map[index].length;i++){
      33.              if(map[index][i] > 0 && !bool[i]){
      34.                  node node = new node(i,length+map[index][i]);
      35.                  if(len[i] > node.length){    //需要更新节点的时候更新节点并加入队列
      36.                      len[i] = node.length;
      37.                      q1.add(node);
      38.                  }
      39.              }
      40.          }
      41.      }
      42.      for(int i=0;i<6;i++){
      43.          System.out.println(len[i]);
      44.      }
      45.  }
      47.  static Comparator<node> com = new Comparator<node>(){
      48.      public int compare(node o1,node o2) {
      49.          return o1.length - o2.length;
      50.      }
      51.  };
      53.  private static void initmap(int[][] map) {
      54.      map[0][1] = 2; map[0][2] = 3; map[0][3] = 6;
      55.      map[1][0] = 2; map[1][4] = 4; map[1][5] = 6;
      56.      map[2][0] = 3; map[2][3] = 2;
      57.      map[3][0] = 6; map[3][2] = 2; map[3][4] = 1; map[3][5] = 3;
      58.      map[4][1] = 4; map[4][3] = 1;
      59.      map[5][1] = 6; map[5][3] = 3;    
      60.  }
      61. }

    • 复杂度

      • 时间复杂度 O(N2)