Author: devangini123

🌙 Dijkstra’s Algorithm Code JavaScript Python Java C++ C C# class MinHeap { constructor() { this.heap = []; } parent(i) { return Math.floor((i – 1) / 2); } left(i) { return 2 * i + 1; } right(i) { return 2 * i + 2; } size() { return this.heap.length; } swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; } push(pair) { this.heap.push(pair); this.heapifyUp(); } heapifyUp() { let i = this.heap.length – 1; while (i > 0 && this.heap[i][0] this.heap[this.parent(i)][0]) { this.swap(i, this.parent(i)); i = this.parent(i); } } pop() { if (this.heap.length === 0) return null; if (this.heap.length === 1)…

🌙 Shortest Path – Bellman Ford Algorithm It handles negative edges. Relaxation is the process of trying to improve (reduce) the shortest distance to a vertex using an edge. How Relaxation Works? For an edge u → v with weight w: If distance[u] + w < distance[v] distance[v] = distance[u] + w Why relaxation is repeated in Bellman–Ford? Bellman–Ford relaxes all edges V−1 times. Because the longest possible shortest path can have at most V−1 edges. Each relaxation gradually propagates shorter paths across the graph. First Relaxation Process Updated Values: Second Relaxation Process Updated Values: Third Relaxation Process Updated Values:…

🌙 Code JavaScript Python Java C++ C C# function bellmanFord(edges, V, src) { const dist = new Array(V).fill(Infinity); dist[src] = 0; // Relax edges V-1 times for (let i = 0; i < V - 1; i++) { let updated = false; for (let [u, v, w] of edges) { if (dist[u] !== Infinity && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; updated = true; } } // Early stopping if no update happened if (!updated) break; } // Check for negative weight cycle for (let [u, v, w] of edges) { if (dist[u] !== Infinity…

🌙 Shortest Path [Unweighted Graph] Here, We have to do ‘Level Order Traversal’ Code JavaScript Python Java C++ C C# function shortestDistance(graph, src){ let n = graph.length; const dist = new Array(n).fill(Infinity); dist[src] = 0; let q = [src]; while(q.length) { let curr = q.shift(); for(let neighbor of graph[curr]) { if(dist[neighbor] == Infinity) { dist[neighbor] = dist[curr] + 1; q.push(neighbor); } } } return dist; } const graph = [ [1, 2], // 0 [3], // 1 [4], // 2 [5], // 3 [3], // 4 [] // 5 ]; from collections import deque def shortest_distance(graph, src): n = len(graph)…

🌙 Shortest Path Algorithms BFS (Unweighted Graph): It is used to calculate the distance between source and destination in Unweighted (no weights on edges) graph. Dijkstra’s (Weighted): It is used to calculates distance in Weighted Graph. It uses Priority Queue and Greedy Algorithm. Drawback: It doesn’t work on the negative weight edges. Bellman–Ford Algorithm (Weighted + Negative): It calculates distance for the Weighted and Negative Edges as well. Note: These above three algorithms are the ‘Single Source Shortest Path’ Algorithm. Floyd–Warshall (All pairs shortest path): It calculates all pairs of shortest path algorithm.

🌙 Kahn’s Algorithm (BFS) (Topological Sort) [DAG] It is a linear ordering of nodes of a DAG(Directed Acyclic Graph) such that for every directed edge (u -> v), node u comes before v. Example An adjacency list represents a graph. const adj = [ [], // 0 [], // 1 [3], // 2 -> 3 [1], // 3 -> 1 [0, 1], // 4 -> 0, 1 [0, 2] // 5 -> 0, 2 ] Representation 5, 0, 2, 3, 1, 4 Indegree Node 0 → indegree 2 Node 1 → indegree 2 Node 2 → indegree 1 Node 3…

🌙 Topological Sort It is a linear ordering of nodes of a DAG(Directed Acyclic Graph) such that for every directed edge (u -> v), node u comes before v. Example An adjacency list represents a graph. const adj = [ [], // 0 [], // 1 [3], // 2 -> 3 [1], // 3 -> 1 [0, 1], // 4 -> 0, 1 [0, 2] // 5 -> 0, 2 ] Representation 5, 0, 2, 3, 1, 4 Code JavaScript Python Java C++ C C# function topologicalSortDFS(n, graph) { let ans = []; let visited = new Set(); function dfs(curr)…

🌙 Detect Cycle in Undirected Connected Graph Example: 1 True Example: 2 False Example: 3 True Adjacent Lists 0: 1 1: 4, 2 2: 1, 3 3: 2, 4 4: 1, 3 Visited nodes: [0, 1, 4, 3, 2] So, It’s not possible. Hence It is not a cycle. Find Cycle ? Note: To keep a track of parent of each node. Parent: Start from Node ‘A’ A: Null B: A C: A D: C E: D H: E G: E F: H A cycle exists if: visited[node] == true AND node != parent Code JavaScript Python Java C++ C…

🌙 Problem Statement You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. You may assume all tickets form at least one valid…

🌙 Problem Statement Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n – 1, find all possible paths from node 0 to node n – 1 and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]). Example 1: Input: graph = [[1,2],[3],[3],[]] Output: [[0,1,3],[0,2,3]] Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3. – 0 → 1 → 2 – 0…