DEV Community

Nihal Agarwal
Nihal Agarwal

Posted on

3 3

Problem's faced in Dijkstra's Java Code || Leetcode

When I am solving questions on Dijkstra's, I had basically two-way (or Java template) to write code for Dijkstra's, but for some questions, problem solved by both ways (or Dijkstra's Java templates) (https://leetcode.com/problems/network-delay-time/) are accepted and for some (e.g., https://leetcode.com/problems/path-with-minimum-effort/), anyone is able to solve the question.

For a graph (represented in Adjacency List):

ArrayList<int[]>[] graph = new ArrayList[n]; // n represents number of nodes.
Enter fullscreen mode Exit fullscreen mode

1. Dijkstra's - One way

boolean[] vis = new boolean[n];
int[] dist = new int[n];
Arrays.fill( dist, Integer.MAX_VALUE );

PriorityQueue<Integer> q = new PriorityQueue<>( (a,b) -> dist[a] - dist[b] );
q.add( 0 ); // Starting node
dist[start] = 0;

 while( !q.isEmpty() )
 {
     int node = q.poll();

     if( vis[node] )
         continue;
     vis[node] = true;

     // traversing neighboours
     for( int[] nb : graph[node] )
     {
         int node2 = nb[0];
         int weight = nb[1];
         if( !vis[node2] && dist[node2] > dist[node] + weight )
         {
             dist[node2] = dist[node] + weight;
             q.add( node2 );
         }
     }
 }
Enter fullscreen mode Exit fullscreen mode

2. Dijkstra's - Second way

 boolean[] vis = new boolean[n];
 int[] dist = new int[n];
 Arrays.fill( dist, Integer.MAX_VALUE );

 PriorityQueue<int[]> q = new PriorityQueue<>( (a,b) -> a[1] - b[1] );
 q.add( new int[2] ); // Starting node
 dist[start] = 0;

 while( !q.isEmpty() )
 {
     int node = q.peek()[0];
     int dis = q.peek()[1];

     if( vis[node] )
         continue;
     vis[node] = true;

     // traversing neighboours
     for( int[] nb : graph[node] )
     {
         int node2 = nb[0];
         int weight = nb[1];
         if( !vis[node2] && dist[node2] > dis + weight )
         {
             dist[node2] = dis + weight;
             q.add( new int[] { node2, dist[node2] } );
         }
     }
 }
Enter fullscreen mode Exit fullscreen mode

Can anyone, help me to know which is the right way (1st or 2nd).

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More