力扣1514——概率最大的路径

但很可惜，超时了。我想了一下，应该是因为没有借用之前已经计算出来的结果，因此比较浪费时间。

其时间复杂度取决于边的数量，假设边的数量是 m ，则时间复杂度为O(m^2)。

而边 m 与点 n 的关系，m 最小是 0（也就是点之间没有线），最大是 (n - 1) * n / 2，每个点之间都有连线。

因此可以预见，这样的算法效率确实很差。

Dijkstra (迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

注意该算法要求图中不存在负权边。

设 G=(V,E) 是一个带权有向图，把图中顶点集合 V 分成两组：

第一组为已求出最短路径的顶点集合（用 S 表示，初始时 S 中只有一个源点，以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了）。

第二组为其余未确定最短路径的顶点集合（用 U 表示），按最短路径长度的递增次序依次把第二组的顶点加入 S 中。

在加入的过程中，总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度。

此外，每个顶点对应一个距离，S 中的顶点的距离就是从 v 到此顶点的最短路径长度。U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。

1. 初始时，S 只包含源点，即 S ＝{v}，v 的距离为0。U 包含除 v 外的其他顶点，即: U ={其余顶点}，若 v 与 U 中顶点 u 有边，则正常有权值，若u不是v的出边邻接点，则权值为∞。
2. 从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
3. 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
4. 重复步骤b和c直到所有顶点都包含在S中。

执行动画过程如下图

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
 // records[i]代表点i相邻的所有点，以及其概率
 List> allRecords = new ArrayList<>(n + 1);
 for (int i = 0; i < n + 1; i++) {
     allRecords.add(new linkedList<>());
 }
 // 构造每个点的相连关系
 for (int i = 0; i < edges.length; i++) {
     int[] edge = edges[i];
     List records = allRecords.get(edge[0]);
     records.add(new Record(edge[1], succProb[i]));
     
     records = allRecords.get(edge[1]);
     records.add(new Record(edge[0], succProb[i]));
 }

 // 利用广度优先搜索，进行遍历
 // 借用优先队列，保证优先遍历当前概率高的
 PriorityQueue queue = new PriorityQueue<>();
 // 记录从start到每一个点的概率
 double[] result = new double[n];
 // 从start开始遍历
 queue.offer(new Record(start, 1));
 result[start] = 1;
 // 开始
 while (!queue.isEmpty()) {
     // 当前节点
     Record record = queue.poll();
     int node = record.node;
     double prob = record.prob;
     // 获取当前点所能达到的其他节点
     List otherNodes = allRecords.get(node);
     // 遍历其余节点
     for (Record next : otherNodes) {
  int nextNode = next.node;
  double nextProb = prob * next.prob;
  // 如果当前计算出的概率，小于等于之前计算的概率
  if (nextProb <= result[nextNode]) {
      // 那么就没有必要继续算了，直接用之前的即可
      continue;
  }
  
  // 更新概率
  result[nextNode] = nextProb;
  // 如果已到结尾或者当前的概率已经比到end的小
  if (nextNode == end || nextProb < result[end]) {
      // 那么也没有必要继续了
      continue;
  }

  // 添加节点
  queue.offer(new Record(nextNode, nextProb));
     }
 }

 return result[end];
    }

    class Record implements Comparable {
 int node;
 double prob;
 public Record(int node, double prob) {
     this.node = node;
     this.prob = prob;
 }

 @Override
 public int compareTo(Record other) {
     if (other == null) {
  return -1;
     }

     if (this.prob == other.prob) {
  return this.node - other.node;
     }

     return this.prob - other.prob > 0 ? -1 : 1;
 }
    }
}

class Solution {
  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    // 记录结果
    double[] result = new double[n];
    // 起点
    result[start] = 1;
    // 从start点出发，先更新直接与start点相连的点的概率，然后逐步更新，直到不需要更新为止
    while (true) {
      // 是否有过变动
      boolean changed = false;
      // 遍历所有边
      for (int j = 0; j < edges.length; j++) {
 int[] edge = edges[j];
 // 如果从当前点edge[0]出发，到edge[1]的概率，大于之前记录的结果
 if (result[edge[0]] * succProb[j] > result[edge[1]]) {
   // 则更新
   result[edge[1]] = result[edges[j][0]] * succProb[j];
   changed = true;
 }
 // 因为是无向图,所以再反向遍历
 if (result[edge[1]] * succProb[j] > result[edge[0]]) {
   result[edge[0]] = result[edge[1]] * succProb[j];
   changed = true;
 }
      }
      // 一遍未修改则表示图已遍历完成
      if (!changed) {
 break;
      }
    }
    return result[end];
  }

}