Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package nuparu.dijkstra;
- import java.util.Arrays;
- public class Main {
- public static void main(String[] args) {
- Integer[][] matrix = {
- {0,5,3,4,null,null},
- {5,0,1,null,3, null},
- {3,1,0,1,10,null},
- {4,null,1,0,6,null},
- {null,3,10,6,0,null},
- {null,null,null,null,null,null}
- };
- int start = 0;
- int nodesCount = matrix.length;
- int[] distances = new int[nodesCount];
- Arrays.fill(distances, Integer.MAX_VALUE);
- boolean[] processed = new boolean[nodesCount];
- Arrays.fill(processed,false);
- distances[start] = 0;
- while (true){
- int smallest = getNodeWithSmallestValue(distances,processed);
- if(smallest == -1) break;
- for(int i = 0; i < distances.length; i++){
- if(processed[i]) continue;
- Integer edge = matrix[i][smallest];
- if(edge != null){
- int newDst = distances[smallest]+edge.intValue();
- if(newDst < distances[i]){
- distances[i] = newDst;
- }
- }
- }
- processed[smallest] = true;
- }
- for(int i = 0; i < distances.length; i++){
- System.out.println("Distance of " + i + " is " + distances[i]);
- }
- }
- public static int getNodeWithSmallestValue(int[] nodes, boolean[] processed){
- int min = -1;
- for(int i = 0; i < nodes.length; i++){
- int node = nodes[i];
- if(!processed[i] && (min == -1 || node < nodes[min])){
- min = i;
- }
- }
- return min;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement