1514.path-with-maximum-probability.md

1514. Path with Maximum Probability

Dijkstra's Algorithm

fun dijkstra1(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start: Int, end: Int): Double {
    val graph = buildGraph(n, edges, succProb)

    val probMat = DoubleArray(n)
    val heap = PriorityQueue(compareByDescending<Pair<Double, Int>> { it.first })
    heap.add(1.0 to start)
    probMat[start] = 1.0
    while (heap.isNotEmpty()) {
        val (prob, vertex) = heap.poll()
        if (prob < probMat[vertex]) continue
        if (vertex == end) return prob
        graph[vertex].forEach { adj ->
            if (probMat[adj.vertex] < probMat[vertex] * adj.weight) {
                probMat[adj.vertex] = probMat[vertex] * adj.weight
                heap.add(probMat[adj.vertex] to adj.vertex)
            }
        }
    }
    return 0.0
}

private fun buildGraph(n: Int, edges: Array<IntArray>, succProb: DoubleArray): Array<MutableList<Edge>> {
    val adjList = Array(n) { mutableListOf<Edge>() }
    for (i in edges.indices) {
        val (a, b) = edges[i]
        val prob = succProb[i]
        adjList[a].add(Edge(b, prob))
        adjList[b].add(Edge(a, prob))
    }
    return adjList
}

TODO: Review the notes + implementations

Shortest Path Faster Algorithm (SPFA)

Since the weight of each edges is [0, 1], the probability of the path will be the same or less than the previous path. We're finding the maximum probability, so we're actually finding the shortest path. We can use BFS to traverse the graph and update the probability of each node.

data class GraphNode(
    val toNode: Int, // indegree node
    val prob: Double // probability of the indegree edge
)

class Solution {
    fun maxProbability(n: Int, edges: Array<IntArray>, succProb: DoubleArray, start_node: Int, end_node: Int): Double {
        val graph = buildGraph(edges, succProb)
        val prob = DoubleArray(n)

        // Remember to set the start node to 1.0
        prob[start_node] = 1.0
        val queue = ArrayDeque<Int>()
        queue.addLast(start_node)
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            graph[node]?.forEach { adj ->
                if (prob[adj.toNode] < prob[node] * adj.prob) {
                    prob[adj.toNode] = prob[node] * adj.prob
                    queue.addLast(adj.toNode)
                }
            }
        }
        return prob[end_node]
    }

    private fun buildGraph(edges: Array<IntArray>, succProb: DoubleArray): HashMap<Int, HashSet<GraphNode>> {
        val graph = HashMap<Int, HashSet<GraphNode>>()
        for (i in 0 until edges.size) {
            val edge = edges[i]
            val prob = succProb[i]
            if (!graph.containsKey(edge[0])) graph[edge[0]] = HashSet<GraphNode>()
            if (!graph.containsKey(edge[1])) graph[edge[1]] = HashSet<GraphNode>()

            graph[edge[0]]!!.add(GraphNode(edge[1], prob))
            graph[edge[1]]!!.add(GraphNode(edge[0], prob))
        }
        return graph
    }
}