I am having hard time in understanding the runtime of Dijkstra’s algorithm. I couldn’t get how the complexity of Dijkstra’s is E Log(V).
For the given graph, vertex 3 gets inserted twice in the priority queue, so how the size of PQ can not grow beyond |V|.
public class Dijkstra {
public static void main(String args[]) {
Dijkstra sol = new Dijkstra();
System.out.println(sol.networkDelayTime(new int[][]{
{1, 2, 1},
{1, 5, 3},
{1, 4, 2},
{2, 3, 6},
{5, 3, 1},
{4, 2, 7},
}, 5, 1));
}
public int[] dijkstra(int[][] times, int N, int K) {
Graph g = new Graph(N, times);
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
int distance[] = new int[N + 1];
boolean visited[] = new boolean[N + 1];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[K] = 0;
pq.offer(new int[]{K, 0});
int time = 0;
while (!pq.isEmpty()) {
int node[] = pq.poll();
List<int[]> neighbours = g.neighbours(node[0]);
visited[node[0]] = true;
for (int[] neighbour : neighbours) {
int v = neighbour[0];
int w = neighbour[1];
if (!visited[v] && distance[v] > node[1] + w) {
distance[v] = node[1] + w;
pq.offer(new int[]{v, distance[v]});
}
}
}
return distance;
}
private static class Graph {
List<List<int[]>> adj = new ArrayList<>();
public Graph(int n, int edges[][]) {
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
}
List<int[]> neighbours(int u) {
return adj.get(u);
}
}
}