# LEETCODE 1514. Path with Maximum Probability 解题思路分析

```输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

```输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2

```输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

• 2 <= n <= 10^4
• 0 <= start, end < n
• start != end
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• 每两个节点之间最多有一条边

```public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<double[]>[] map=new ArrayList[n]; // 构建图形结构
for(int i=0;i<edges.length;i++){
int[]edge=edges[i];
if(map[edge[0]]==null) map[edge[0]]=new ArrayList<>();
if(map[edge[1]]==null) map[edge[1]]=new ArrayList<>();
}
// 记录访问过的节点
// memo[i]代表从起始节点到i节点间的最大概率
double[] memo=new double[n];
// 将起始节点，加入Queue，1d代表从start到start的概率为1
q.offer(new double[]{start,1d});
memo[start]=1; // 从start到start的概率为1
double res=0; // 返回结果
while(q.size()>0){ // 以下为标准bfs
double[] d=q.poll(); // 取出一个节点
int node=(int)d[0]; // 节点下标
double sp=d[1]; // 当前路径走到该节点时的概率
if(node==end){ // 如果当前节点为目标节点
res=Math.max(res,sp); // 用当前概率全局更新最大概率
continue; // 结束当前路径
}
// 如果当前路径没有其他相邻节点，跳过
if(map[node]==null) continue;
// 循环当前节点的所有相邻节点
for(double[] next : map[node]){
int nextNode=(int)next[0]; // 相邻接点下标
double nextSp = sp*next[1]; // 当前路径走到相邻接点时的概率
if(nextSp>memo[nextNode]){ // 如果概率大于数组的概率
memo[nextNode]=nextSp; // 更新到相邻接点的最大概率
q.offer(new double[]{nextNode, nextSp}); // 走到下一个节点
}
}
}
return res;
}```

Runtime: 60 ms, faster than 86.42% of Java online submissions for Path with Maximum Probability.

Memory Usage: 103.8 MB, less than 100.00% of Java online submissions for Path with Maximum Probability.

```double[] memo;
double res=0;
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<double[]>[] map=new ArrayList[n];
memo=new double[n];
memo[start]=1;
for(int i=0;i<edges.length;i++){
int[]edge=edges[i];
if(map[edge[0]]==null) map[edge[0]]=new ArrayList<>();
if(map[edge[1]]==null) map[edge[1]]=new ArrayList<>();
}
dfs(map,start,end, 1);
return res;
}

void dfs(List<double[]>[] map,int current,int end, double sp){
if(current==end){
res=Math.max(res, sp);
return;
}
if(map[current]==null) return;
for(double[] next:map[current]){
int nextNode=(int)next[0];
double nextSp=next[1]*sp;
if(nextSp>memo[nextNode]){
memo[nextNode]=nextSp;
dfs(map, nextNode, end, nextSp);
}
}
}```