TODO: Review the notes + implementations
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
}
}