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^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= 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

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more