Advertisement
Nuparu00

dijkstra no oop

Feb 18th, 2022
767
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.77 KB | None | 0 0
  1. package nuparu.dijkstra;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class Main {
  6.  
  7.     public static void main(String[] args) {
  8.  
  9.         Integer[][] matrix = {
  10.                 {0,5,3,4,null,null},
  11.                 {5,0,1,null,3, null},
  12.                 {3,1,0,1,10,null},
  13.                 {4,null,1,0,6,null},
  14.                 {null,3,10,6,0,null},
  15.                 {null,null,null,null,null,null}
  16.         };
  17.  
  18.         int start = 0;
  19.         int nodesCount = matrix.length;
  20.         int[] distances = new int[nodesCount];
  21.         Arrays.fill(distances, Integer.MAX_VALUE);
  22.  
  23.         boolean[] processed = new boolean[nodesCount];
  24.         Arrays.fill(processed,false);
  25.  
  26.         distances[start] = 0;
  27.  
  28.  
  29.         while (true){
  30.             int smallest = getNodeWithSmallestValue(distances,processed);
  31.             if(smallest == -1) break;
  32.  
  33.             for(int i = 0; i < distances.length; i++){
  34.                 if(processed[i]) continue;
  35.                 Integer edge = matrix[i][smallest];
  36.                 if(edge != null){
  37.                     int newDst = distances[smallest]+edge.intValue();
  38.                     if(newDst < distances[i]){
  39.                         distances[i] = newDst;
  40.                     }
  41.                 }
  42.             }
  43.             processed[smallest] = true;
  44.  
  45.         }
  46.  
  47.         for(int i = 0; i < distances.length; i++){
  48.             System.out.println("Distance of " + i + " is " + distances[i]);
  49.         }
  50.  
  51.     }
  52.  
  53.     public static int getNodeWithSmallestValue(int[] nodes, boolean[] processed){
  54.         int min = -1;
  55.         for(int i = 0; i < nodes.length; i++){
  56.             int node = nodes[i];
  57.             if(!processed[i] && (min == -1 || node < nodes[min])){
  58.                 min = i;
  59.             }
  60.         }
  61.         return min;
  62.     }
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement