NetworkDelayTime1.java

class Solution {
     public int networkDelayTime(int[][] times, int N, int K) {
        int V = N + 1;
        int[][] adj = new int[V][V];
        for (int i = 1; i < V; i++)
            for (int j = 1; j < V; j++)
                adj[i][j] = -1;
        for (int[] conn : times) {
            adj[conn[0]][conn[1]] = conn[2];
        }

        return dijkstra(adj, V, K);
    }
    
    public int dijkstra(int[][] adj, int V, int K) {

        int[] dist = new int[V];
        boolean[] visited = new boolean[V];
        for (int i = 1; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[K] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistVertex(dist, visited);
            if (u == -1) return -1;
            visited[u] = true;

            for (int v = 1; v < V; v++) {
                if (!visited[v] && adj[u][v] >= 0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u] + adj[u][v] < dist[v]) {
                    dist[v] = dist[u] + adj[u][v];
                }
            }
        }

        int maxDist = Integer.MIN_VALUE;
        for (int v = 1; v < V; v++) {
            if (dist[v] < Integer.MAX_VALUE)
                maxDist = Math.max(maxDist, dist[v]);
        }
        return maxDist;
    }

    private int minDistVertex(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE, minV = -1;
        for (int v = 1; v < dist.length; v++) {
            if (!visited[v] && dist[v] < min) {
                minV = v;
                min = dist[v];
            }
        }
        return minV;
    }
}