An Interest In:
Web News this Week
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
- April 11, 2024
- April 10, 2024
- April 9, 2024
May 29, 2022 10:51 pm GMT
Original Link: https://dev.to/nihalagarwal/dijkstras-java-code-5can
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.
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 nodedist[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 ); } } }
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] } ); } } }
Can anyone, help me to know which is the right way (1st or 2nd).
Original Link: https://dev.to/nihalagarwal/dijkstras-java-code-5can
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To