Skip to content

Files

Latest commit

caba0a4 · May 27, 2025

History

History
49 lines (42 loc) · 1.91 KB

1514.path-with-maximum-probability.md

File metadata and controls

49 lines (42 loc) · 1.91 KB

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
    }
}