Classic Dijkstra
Dijkstra invented one of the most classic algorithms to find the min/max path in a graph - we call it today simply Dijkstra's Algorithm.
This problem requires a classic use of Dijkstra's Algorithm: https://leetcode.com/problems/path-with-maximum-probability/
1514. Path with Maximum Probability
Medium
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
Constraints:
2 <= n <= 10^40 <= start, end < nstart != end0 <= a, b < na != b0 <= succProb.length == edges.length <= 2*10^40 <= succProb[i] <= 1- There is at most one edge between every two nodes.
Accepted
6,747
Submissions
20,137
In a nutshell, Dijkstra's can be explained in the following pseudo-code:
A) Build or use a Priority Queue
B) For the problem here, the priority will be a double and it will be in descend order
C) Enqueue the start index, with a probability 1
D) While the queue isn't empty
E) Dequeue, process (check for the end) and mark as visited
F) Get the neighbors
G) For each one, check if it isn't visited and add to the queue with the proper probability
H) Notice that on (G), you do not mark as visited, meaning that the queue can contain multiple instances of the same node
Works well, code is below, cheers, ACC.
public class Solution
{
public double MaxProbability(int n, int[][] edges, double[] succProb, int start, int end)
{
Hashtable graph = new Hashtable();
for (int i = 0; i < edges.Length; i++)
{
if (!graph.ContainsKey(edges[i][0])) graph.Add(edges[i][0], new Hashtable());
Hashtable map = (Hashtable)graph[edges[i][0]];
if (!map.ContainsKey(edges[i][1])) map.Add(edges[i][1], succProb[i]);
if (!graph.ContainsKey(edges[i][1])) graph.Add(edges[i][1], new Hashtable());
map = (Hashtable)graph[edges[i][1]];
if (!map.ContainsKey(edges[i][0])) map.Add(edges[i][0], succProb[i]);
}
if (!graph.ContainsKey(start)) return 0;
Hashtable visited = new Hashtable();
PriorityQueue pQueue = new PriorityQueue();
pQueue.Enqueue(start, 1.0);
while (pQueue.Count > 0)
{
double probability = 0;
int index = (int)pQueue.Dequeue(out probability);
if (index == end) return probability;
if (!visited.Contains(index)) visited.Add(index, true);
if (graph.ContainsKey(index))
{
Hashtable map = (Hashtable)graph[index];
foreach (int neighbor in map.Keys)
{
if (!visited.ContainsKey(neighbor))
{
pQueue.Enqueue(neighbor, probability * (double)map[neighbor]);
}
}
}
}
return 0;
}
/*
public static void Main()
{
Solution sol = new Solution();
}
*/
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private double priority;
public HeapEntry(object item, double priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public double Priority
{
get
{
return priority;
}
}
}
private int count;
private int capacity;
private HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue()
{
capacity = 1000000;
heap = new HeapEntry[capacity];
}
public object Dequeue(out double priority)
{
priority = heap[0].Priority;
object result = heap[0].Item;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, double priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}
private void bubbleUp(int index, HeapEntry he)
{
int parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
while ((index > 0) && (heap[parent].Priority < he.Priority))
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
heap[index] = he;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
if (((child + 1) < count) &&
(heap[child].Priority < heap[child + 1].Priority))
{
child++;
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
}
Comments
Post a Comment