gtblack

Dijkstra Algorithm

May 16th, 2021 (edited)
590
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Dijkstra {
  4.     public static int findShortestPath(int from, int to, int[][] graph) {
  5.         int[] currentWeight = new int[graph.length];
  6.         Arrays.fill(currentWeight, Integer.MAX_VALUE);
  7.         currentWeight[from] = 0;
  8.         Set<Integer> nextNodes = new HashSet<>();
  9.         Set<Integer> visited = new HashSet<>();
  10.         nextNodes.add(from);
  11.         while (!nextNodes.isEmpty()) {
  12.             int current = -1;
  13.             int candidateWeight = Integer.MAX_VALUE;
  14.             for (int candidate : nextNodes) {
  15.                 if (currentWeight[candidate] < candidateWeight) {
  16.                     candidateWeight = currentWeight[candidate];
  17.                     current = candidate;
  18.                 }
  19.             }
  20.             if (current < 0) {
  21.                 break;
  22.             }
  23.             int[] edges = graph[current];
  24.             for (int next = 0; next < edges.length; next++) {
  25.                 if (!visited.contains(next) && edges[next] != 0) {
  26.                     int newWeight = currentWeight[current] + edges[next];
  27.                     currentWeight[next] = Math.min(currentWeight[next], newWeight);
  28.                     nextNodes.add(next);
  29.                 }
  30.             }
  31.             visited.add(current);
  32.             nextNodes.remove(current);
  33.         }
  34.         return currentWeight[to];
  35.     }
  36.  
  37.     public static void main(String[] args) {
  38.         // https://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Dijkstra_Animation.gif/220px-Dijkstra_Animation.gif
  39.         int[][] graph = new int[][]{
  40.             {0, 7, 9, 14, 0, 0},
  41.             {7, 0, 10, 0, 15, 0},
  42.             {9, 10, 0, 2, 11, 0},
  43.             {14, 0, 2, 0, 0, 9},
  44.             {0, 15, 11, 0, 0, 6},
  45.             {0, 0, 0, 9, 6, 0}
  46.         };
  47.         System.out.println(findShortestPath(0, 5, graph));
  48.     }
  49. }
RAW Paste Data