Modify Graph Edge Weights | Using Dijkstra | Thought Process | Leetcode 2699 | codestorywithMIK
449Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 56th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Dijkstra's Algorithm Part - 1 - • Dijkstra's Algorithm | PART-1 | (Micr...
Dijkstra's Algorithm Part - 2 - • Dijkstra's Algorithm | PART-2 | (Micr...
In this video we will try to solve a very good Graph Problem : Modify Graph Edge Weights | Using Dijkstra | Thought Process | Leetcode 2699 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY. It will have full details.
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 : Modify Graph Edge Weights | Using Dijkstra | Thought Process | Leetcode 2699 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/modify-...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Dijkstra's Algorithm: The solution uses Dijkstra's algorithm to compute the shortest path between the source and destination nodes. It first builds an adjacency list from the input edges, ignoring edges with a weight of -1. The algorithm uses a priority queue to efficiently find the shortest paths, updating distances as it explores each node.
Initial Shortest Path Calculation: The shortest path between source and destination is calculated without considering -1 weighted edges. If this shortest path is already shorter than the target, it returns an empty result since it's impossible to achieve the desired distance by modifying the edges.
Edge Weight Adjustment: If the initial shortest distance is not equal to the target, the algorithm iterates through all edges with a weight of -1. It tries to adjust these edge weights to either a large value (if the current shortest path matches the target) or a small value (if it doesn't). After modifying an edge, it recalculates the shortest path to check if it matches the target. If a match is found, the algorithm adjusts the edge weights to precisely meet the target.
Final Check: If after all adjustments the target distance is achieved, the modified edges are returned; otherwise, an empty result is returned indicating it's not possible to meet the target distance.
This approach efficiently combines Dijkstra's algorithm with edge weight adjustments to achieve the desired path length in the graph.
✨ Timelines✨
00:00 - Introduction
0:48 - Problem Explanation
5:55 - Thought Process
20:49 - Story Points
24:36 - Important Point
29:20 - Story To Code
#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