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).

AWS Security LIVE! Stream

Stream AWS Security LIVE!

The best security feels invisible. Learn how solutions from AWS and AWS Partners make it a reality on Security LIVE!

Learn More

Top comments (0)

Quickstart image

Django MongoDB Backend Quickstart! A Step-by-Step Tutorial

Get up and running with the new Django MongoDB Backend Python library! This tutorial covers creating a Django application, connecting it to MongoDB Atlas, performing CRUD operations, and configuring the Django admin for MongoDB.

Watch full video β†’

πŸ‘‹ Kindness is contagious

Engage with a wealth of insights in this thoughtful article, valued within the supportive DEV Community. Coders of every background are welcome to join in and add to our collective wisdom.

A sincere "thank you" often brightens someone’s day. Share your gratitude in the comments below!

On DEV, the act of sharing knowledge eases our journey and fortifies our community ties. Found value in this? A quick thank you to the author can make a significant impact.

Okay