G-32. Dijkstra's Algorithm - Using Priority Queue - C++ and Java - Part 1

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞

Do follow me on Instagram: striver_79

understood sir :)

I am guessing Video 28 was Dijkstra with Queue?

y no visited array here btw?

Nice Video

You are a Masterpeice!!

shortest path to all the nodes using dikjstra and minHeap.(JAVA)


import java.util.*;

class point {
int node;
int weight;

public point(int node, int weight) {
this.node = node;
this.weight = weight;
}

public int hashCode() {
return Objects.hash(this.node, this.weight);
}

public boolean equals(Object obj) {
point p = (point) obj;
if (this.node == p.node) {
return true;
}
return false;
}
}

public class Dijastra {

public static void dijastra(HashMap<Integer, List<point>> adjList, int[] dist, PriorityQueue<point> minHeap) {
point p = minHeap.poll();
if (p == null) {
return;
}
while (p.weight > dist[p.node]) {
p = minHeap.poll();
if (p == null) {
return;
}
}
int node = p.node;
dist[node] = p.weight;

adjList.get(node).forEach((neighbour) -> {
neighbour.weight += dist[node];
minHeap.add(neighbour);
});
dijastra(adjList, dist, minHeap);
}

public static void main(String[] args) {
PriorityQueue<point> minHeap = new PriorityQueue<>((a, b) -> {
return Integer.compare(a.weight, b.weight);
});
minHeap.add(new point(0, 0));
HashMap<Integer, List<point>> adjList = new HashMap<>();
int[] dist = new int[] { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE,
Integer.MAX_VALUE, Integer.MAX_VALUE };
adjList.put(0, List.of(new point(1, 4), new point(2, 4)));

adjList.put(1, List.of(new point(0, 4), new point(2, 2)));

adjList.put(2, List.of(new point(0, 4), new point(3, 3), new point(1, 2), new point(5, 6), new point(3, 3),
new point(4, 1)));

adjList.put(3, List.of(new point(2, 3), new point(5, 2)));
adjList.put(4, List.of(new point(2, 1), new point(5, 3)));
adjList.put(5, List.of(new point(3, 2), new point(2, 6), new point(4, 3)));
dijastra(adjList, dist, minHeap);
for (int i : dist) {
System.out.println(i);
}
}
}

One suggestion in java code.. Instead of doing 2 operations I.E. peek() and remove() at line number 81,82& 83, we can do one operation pop().. Just an FYI for other java codes... Happy coding.. 👍

Understood

UNDERSTOOD.

Thank you!

I implemented it on my own and it worked without storing the distance on the priority queue. I only stored the nodes themselves. I also used a Pair class to store (dest,weight)

Revision I: Easy Peasy

Sep'6, 2023 10:58 pm

i wanna know which notes app do you use

In this implementation it was extremely difficult to figure out the complexity.
When we use a visited array, it become clear that a node may be queued multiple times but its neighbors will only be processed once.
Because the first occurrence of duplicate node in the queue will have the lightest path and mark the node as visited. Eliminating the need for redundancies to be processed.

Why dont we consider visited node here?

New beard looking good

Habibi ye bhi kamal video banti ... bahut accha bahut accha

Understoood <3

us

understood

can anyone say what is the need for this algorithm because we already found the shortest path in previous lectures of striver??????

understood

understood

Understood....

Understood !

Thank You

great work 👏

Understood

We have not handled the case of Unreachable nodes in this question

yes

is it applicable for directed graph?

Apart from weighted edges what is the difference between this and approach in l28

understood

understood ❤

understood!!

Understood !!

by dijkstra can directed graph with negative edge be solved .? in this video undirected graph is used. please anyone answer

Understood 😊

understood

Understood❤

🐐

understood striver!!!

1 silly question, if you have observed striver has put distance first in priority_queue due to ease of sorting as the values are sorted based on first value, but I put distance second, and wrote a comparison function from there I observed that if i return bool operator()(pii a, pii b) {
return a.second < b.second;
} its giving me TLE, isn't the first value should be smaller that second when implementing min_heap, if i return opposite, its running fine, anyone has idea about it?

Understood 👍

UNDERSTOOD

❤

excellent explanation. Lucky to find your channel.❤

us