Dijkstra Shortest Path Algorithm in Java

A standard rule of thumb that is followed for solving shortest path problems is that we mostly use Breadth-first search for unweighted graphs and use Dijkstra’s algorithm for weighted graphs. An implied condition to apply the Dijkstra’s algorithm is that the weights of the graph must be positive. If the graph has negative weights and can have negative weighted cycles, we would have to employ another algorithm called the Bellman Ford’s.

So I was solving the problem number 1514 on leetcode and was faced with the graph problem.

Path with Maximum Probability - LeetCode

Here according to the hints, I needed to use Dijkstra’s algorithm too.

So here is some reference materials for the algorithm

Dijkstra Algorithm in Java | Baeldung

Overview of Dijkstra's Algorithm | Baeldung on Computer Science

https://www.youtube.com/watch?v=KyRSJRMz818

The last one is my favorite.

import org.antlr.v4.misc.Graph;
import org.apache.poi.ss.formula.functions.Index;

import java.util.*;

public class Probability {
    class Node{
        public Node(int number){
            this.number=number;
        }

        @Override
        public String toString() {
//            System.out.println("Num: "+this.number+" adjacent "+adjacentNodes+" distance: "+distance);
            return "Num: "+this.number+" adjacent "+adjacentNodes+" prob: "+prob;
        }

        public double prob=0;
        public int number;
        Map<Integer, Double> adjacentNodes = new HashMap<>();
        public void addDestination(Integer destination, double distance) {
            adjacentNodes.put(destination, distance);
        }
    }
    Queue<Node> prio=new PriorityQueue<>(Comparator.comparingDouble(o -> -o.prob));
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        Node[] array=new Node[n];
        for (int i = 0; i < n; i++) {
            array[i]=new Node(i);
        }
        for (int i = 0; i < edges.length; i++) {
            array[edges[i][0]].addDestination(edges[i][1],succProb[i]);
            array[edges[i][1]].addDestination(edges[i][0],succProb[i]);
        }
        Set<Node> unvisited=new HashSet<>();
        for (Node node:array
             ) {
            System.out.println(node.toString());
        }
        Set<Integer> visited=new HashSet<>();
        array[start].prob=1;
        prio.add(array[start]);

        while(!prio.isEmpty()){
            Node currentNode=prio.remove();
            System.out.println("currentNode "+currentNode.toString());
            if(currentNode.number==end){
//                System.out.println(currentNode.prob);
                return currentNode.prob;
            }
            for (Integer index:currentNode.adjacentNodes.keySet()
                 ) {
                if(!visited.contains(index)) {
                    if (array[index].prob < (currentNode.adjacentNodes.get(index)*currentNode.prob)) {
                        array[index].prob = (currentNode.adjacentNodes.get(index)*currentNode.prob);
                    }
                    prio.add(array[index]);
                }
            }
            visited.add(currentNode.number);
        }
        return 0;
    }



    public static void main(String[] args) {
        double v = new Probability().maxProbability(3, new int[][]{{0, 1}, {1, 2}, {0, 2}},new double[]{0.5,0.5,0.2},0,2);
    }
}

And here is my code for the algo.

If the node is coming from the priority queue that means all the other nodes in the priority queue are having higher distances and it would mean that it is the minimum path traced to reach the node.

Why it doesn’t work with negative values?
or does it work sometimes and sometimes not?
https://youtu.be/R3g2SSlyY_0