ダイクストラ法

ダイクストラ法で leetCode の問題を解いたので、参考のためにコードをここに残しておく。
Path with Maximum Probability - LeetCode

ポイントは、コード中のコメントに記した。
PriorityQueue(heap) を使っているのは、キューの中で最大確率の (確定できる) ノードから処理するため。

import java.util.*;

public class MaximumProbability {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        // source -> (node, pathProb)
        Map<Integer, List<Neighbor>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            double pathProb = succProb[i];
            graph.computeIfAbsent(a, k -> new ArrayList<>()).add(new Neighbor(b, pathProb));
            graph.computeIfAbsent(b, k -> new ArrayList<>()).add(new Neighbor(a, pathProb));
        }

        double[] maxProb = new double[n];
        maxProb[start] = 1d;

        // maxProb の大きい順
        PriorityQueue<Node> leftTargetQ =
                new PriorityQueue<>((a, b) -> Double.compare(b.maxProb, a.maxProb));
        leftTargetQ.add(new Node(start, 1d));

        while (!leftTargetQ.isEmpty()) {
            Node curNode = leftTargetQ.poll();
            if (curNode.index == end) {
                return curNode.maxProb;
            }

            // curNode の近隣がなくても ヌルポ にならないように、デフォルト値として new ArrayList<>() を突っ込んでいる。
            for (Neighbor neighbor : graph.getOrDefault(curNode.index, new ArrayList<>())) {
                double neighborProb = curNode.maxProb * neighbor.pathProb;
                if (neighborProb > maxProb[neighbor.node]) {
                    // ある node の maxProb が更新されたら、
                    // その node 周辺の node の maxProb が更新されるかもしれないので、再度キューに入れる。
                    maxProb[neighbor.node] = neighborProb;
                    leftTargetQ.add(new Node(neighbor.node, maxProb[neighbor.node]));
                }
            }
        }

        return 0d;
    }

    // 周辺 Node の情報を保持する。
    private static class Neighbor {
        int node;
        double pathProb;

        Neighbor(int node, double pathProb) {
            this.node = node;
            this.pathProb = pathProb;
        }
    }

    // Node の maxProb を保持する。
    private static class Node {
        int index;
        double maxProb;

        Node(int index, double maxProb) {
            this.index = index;
            this.maxProb = maxProb;
        }
    }
}