Find Edges in Shortest Paths | Dijkstra's Algo | Full Intuition | Leetcode 3123 | codestorywithMIK
97Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 46th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Dijkstra's Algo (Part-1) - https://youtu.be/xQ3vjWwFRuI?si=jS8cEE5_8GunYVQd
Dijkstra's Algo (Part-2) - https://youtu.be/3qIoYIMidpc?si=w4veeKIk8SZoTj3p
In this video we will try to solve another very good problem based on Dijkstra's Algorithm : Find Edges in Shortest Paths | Dijkstra's Algorithm | Complete Intuition | Leetcode 3123 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Find Edges in Shortest Paths | Dijkstra's Algorithm | Complete Intuition | Leetcode 3123 | codestorywithMIK
Company Tags : Will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Dijkstra'a%20Based%20Problems/Find%20Edges%20in%20Shortest%20Paths.cpp
Leetcode Link : https://leetcode.com/problems/find-edges-in-shortest-paths/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
The provided code implements an approach to find paths in an undirected graph that satisfy certain conditions. Here's a summary of the approach:
1. **Shortest Path Calculation**: The `getShortestPath` function calculates the shortest distance from a given source node to all other nodes in the graph using Dijkstra's algorithm. It uses a priority queue (`pq`) to prioritize nodes based on their current distance from the source.
2. **Path Evaluation**: The `findAnswer` function constructs the graph from the given list of edges and then computes the shortest paths from both the starting node and the ending node using the `getShortestPath` function.
3. **Path Validation**: For each edge in the list of edges, the code checks if there exists a path from the starting node to the ending node via the edge such that the sum of distances from the starting node to the edge, from the edge to the ending node, and the weight of the edge itself equals the total shortest distance from the starting node to the ending node. This check is performed in both directions since the edges are undirected.
4. **Result Generation**: The function returns a boolean vector indicating whether each edge satisfies the conditions or not.
Overall, the approach efficiently computes shortest paths in the graph and checks whether certain paths meet the required criteria, providing a solution to the problem at hand.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024