content: package AlgoExSolutions.Hard.DijkstrasAlgorithm;
  
  import java.util.*;
  
  /**
   * * Dijkstra's Algorithm
   */
  class Program {
    /**
     * * O((v + e) * log v) time | O(v) space
     */
    public int[] dijkstrasAlgorithm(int start, int[][][] edges) {
      // Write your code here.
      int len = edges.length;
  
      int[] minDistances = new int[len];
      Arrays.fill(minDistances, Integer.MAX_VALUE);
      minDistances[start] = 0;
  
      List<Item> minDistancesPairs = new ArrayList<>();
      for (int i = 0; i < len; i++) minDistancesPairs.add(new Item(i, Integer.MAX_VALUE));
  
      MinHeap minHeap = new MinHeap(minDistancesPairs);
      minHeap.update(start, 0);
  
      while (!minHeap.isEmpty()) {
        Item minItem = minHeap.remove();
        int srcVertex = minItem.vertex;
        int currentMinDistance = minItem.distance;
  
        if (currentMinDistance == Integer.MAX_VALUE) break;
  
        for (int[] edge : edges[srcVertex]) {
          int destVertex = edge[0];
          int newPathDistance = edge[1] + currentMinDistance;
  
          if (newPathDistance < minDistances[destVertex]) {
            minDistances[destVertex] = newPathDistance;
            minHeap.update(destVertex, newPathDistance);
          }
        }
      }
  
      replaceInfinities(minDistances);
  
      return minDistances;
    }
  
    /**
     * * O(v^2) time | O(v) space
     */
    // public int[] dijkstrasAlgorithm(int start, int[][][] edges) {
    // 	int[] minDistances = new int[edges.length];
    // 	Arrays.fill(minDistances, Integer.MAX_VALUE);
    // 	minDistances[start] = 0;
  
    // 	Set<Integer> visited = new HashSet<>();
  
    // 	while (visited.size() != edges.length) {
    // 		int[] vertexInfo = getVertexWithMinDistance(minDistances, visited);
    // 		int srcVertex = vertexInfo[0], currentMinDistance = vertexInfo[1];
  
    // 		if (currentMinDistance == Integer.MAX_VALUE) break;
  
    // 		visited.add(srcVertex);
  
    // 		for (int[] edge : edges[srcVertex]) {
    // 			int destVertex = edge[0], newPathDistance = edge[1] + currentMinDistance;
  
    // 			if (visited.contains(destVertex)) continue;
  
    // 			if (newPathDistance < minDistances[destVertex])
    // 				minDistances[destVertex] = newPathDistance;
    // 		}
    // 	}
  
    // 	replaceInfinities(minDistances);
  
    //   return minDistances;
    // }
  
    // private int[] getVertexWithMinDistance(int[] distances, Set<Integer> visited) {
    // 	int minVertex = -1, minDistance = Integer.MAX_VALUE;
  
    // 	for (int vertex = 0; vertex < distances.length; vertex++) {
    // 		if (visited.contains(vertex)) continue;
  
    // 		if (distances[vertex] <= minDistance) {
    // 			minDistance = distances[vertex];
    // 			minVertex = vertex;
    // 		}
    // 	}
  
    // 	return new int[] {minVertex, minDistance};
    // }
  
    private void replaceInfinities(int[] distances) {
      for (int idx = 0; idx < distances.length; idx++) {
        if (distances[idx] == Integer.MAX_VALUE) distances[idx] = -1;
      }
    }
  
    static class Item {
      int vertex;
      int distance;
  
      public Item(int vertex, int distance) {
        this.vertex = vertex;
        this.distance = distance;
      }
    }
  
    static class MinHeap {
      Map<Integer, Integer> vertexMap;
      List<Item> heap;
  
      public MinHeap(List<Item> array) {
        vertexMap = buildVertexMap(array);
        heap = buildHeap(array);
      }
  
      private List<Item> buildHeap(List<Item> array) {
        // Write your code here.
        int lastParentIdx = parent(array.size() - 1);
  
        while (lastParentIdx >= 0) {
          siftDown(lastParentIdx, array.size() - 1, array);
          --lastParentIdx;
        }
  
        return array;
      }
  
      private Map<Integer, Integer> buildVertexMap(List<Item> array) {
        Map<Integer, Integer> vertexMap = new HashMap<>();
  
        for (int i = 0; i < array.size(); i++) {
          Item item = array.get(i);
          vertexMap.put(item.vertex, item.vertex);
        }
  
        return vertexMap;
      }
  
      private int parent(int index) {
        return (int) Math.floor((index - 1) / 2);
      }
  
      private int left(int index) {
        return (int) Math.floor((2 * index) + 1);
      }
  
      private int right(int index) {
        return (int) Math.floor((2 * index) + 2);
      }
  
      private void swap(int firstIdx, int secondIdx) {
        vertexMap.put(heap.get(firstIdx).vertex, secondIdx);
        vertexMap.put(heap.get(secondIdx).vertex, firstIdx);
        Item temp = heap.get(firstIdx);
        heap.set(firstIdx, heap.get(secondIdx));
        heap.set(secondIdx, temp);
      }
  
      private void siftDown(int currentIdx, int endIdx, List<Item> heap) {
        // Write your code here.
        int leftIdx = left(currentIdx);
        int rightIdx = right(currentIdx);
        int smallestIdx = currentIdx;
  
        if (leftIdx <= endIdx && heap.get(leftIdx).distance < heap.get(currentIdx).distance)
          smallestIdx = leftIdx;
  
        if (rightIdx <= endIdx && heap.get(rightIdx).distance < heap.get(smallestIdx).distance)
          smallestIdx = rightIdx;
  
        if (smallestIdx != currentIdx) {
          swap(currentIdx, smallestIdx);
          siftDown(smallestIdx, endIdx, heap);
        }
      }
  
      private void siftUp(int currentIdx, List<Item> heap) {
        // Write your code here.
        int parentIdx = parent(currentIdx);
        while (currentIdx > 0 && heap.get(parentIdx).distance > heap.get(currentIdx).distance) {
          swap(currentIdx, parentIdx);
          currentIdx = parentIdx;
          parentIdx = parent(currentIdx);
        }
      }
  
      public Item peek() {
        // Write your code here.
        return heap.get(0);
      }
  
      public Item remove() {
        // Write your code here.
        if (isEmpty()) return null;
  
        swap(0, heap.size() - 1);
        Item lastItem = heap.remove(heap.size() - 1);
  
        vertexMap.remove(lastItem.vertex);
        siftDown(0, heap.size() - 1, heap);
  
        return lastItem;
      }
  
      public void update(int vertex, int value) {
        // Write your code here.
        heap.set(vertexMap.get(vertex), new Item(vertex, value));
        siftUp(vertexMap.get(vertex), heap);
      }
  
      public boolean isEmpty() {
        return heap.size() == 0;
      }
    }
  }
  