Author: devangini123

🌙 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…

🌙 Problem Statement There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n – 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex Ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. Given edges and the integers n, source, and destination, return true if…

🌙 Problem Statement There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n – 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex Ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. Given edges and the integers n, source, and destination, return true if…