Проблемы, возникающие в Java-коде Дийкстры || Leetcode

Когда я решал вопросы по Дейкстре, у меня было в основном два пути (или Java шаблона) для написания кода Дейкстры, но для некоторых вопросов принимаются задачи, решенные обоими путями (или Java шаблонами Дейкстры) (https://leetcode.com/problems/network-delay-time/), а для некоторых (например, https://leetcode.com/problems/path-with-minimum-effort/), любой может решить вопрос.

Для графа (представленного в 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 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 );
         }
     }
 }

Войти в полноэкранный режим Выход из полноэкранного режима

2. Дейкстры – второй путь

 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] } );
         }
     }
 }

Войти в полноэкранный режим Выйти из полноэкранного режима

Может ли кто-нибудь помочь мне узнать, какой способ является правильным (первый или второй).

Проблемы, возникающие в Java-коде Дийкстры || Leetcode

Рекомендуем почитать: