LeetCode 3650 | Minimum Cost Path with Edge Reversals | Java | Medium | Dijkstra | CodeByTushu
Description: 🚀 Welcome Back to CodeByTushu!
In today’s video, we solve LeetCode 3650 - Minimum Cost Path with Edge Reversals using Graph and Dijkstra's Algorithm in Java.
We are given a directed weighted graph with n nodes and need to find the minimum cost to travel from node 0 to node n - 1. We have a special switch at each node that allows us to reverse an incoming edge into an outgoing edge at double its original weight. Because all edge weights are strictly positive, any shortest path in the graph is simple and will never visit any node more than once. This means the constraint of using each node's switch at most once is naturally satisfied on any optimal path.
We model this problem elegantly by constructing an augmented graph where each original directed edge from u to v with weight w is accompanied by a virtual reverse edge from v to u with weight 2w. We then run standard Dijkstra's algorithm using a min-heap priority queue from source node 0 to target node n - 1. The algorithm gracefully handles unreachable destinations by returning -1 and runs in optimal O((V + E) log V) time with O(V + E) auxiliary space.
🔥 Problem Highlights
✅ Reversing an incoming edge from u to v into an edge from v to u costs twice the original weight
✅ All weights are strictly positive, guaranteeing that optimal paths are simple paths
✅ Augmented graph approach with virtual reverse edges eliminates state explosion
✅ Min-heap priority queue Dijkstra guarantees minimal cost exploration
✅ Handles disconnected graphs and multiple edges between nodes cleanly
✅ Time Complexity: O((V + E) log V)
✅ Auxiliary Space Complexity: O(V + E)
⏱️ TIMESTAMPS
00:00 Intro
00:58 Problem Understanding
02:28 Key Observation
03:30 Augmented Graph and Dijkstra Approach
04:45 Java Code Walkthrough
06:02 Execution and Test Cases
07:55 Time Complexity Analysis
08:44 Space Complexity Analysis
09:24 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Graph Shortest Path
Dijkstra's Algorithm
Augmented Graph Pattern
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does adding reverse edges with weight twice the original weight not violate the at most once per node switch constraint in Dijkstra's algorithm?
1️⃣ Dijkstra keeps track of a bitmask of used switches for every vertex
2️⃣ All edge weights are positive, so the shortest path is always simple and visits each node at most once
3️⃣ Reverse edges can only be traversed during the first step of Dijkstra
4️⃣ The algorithm resets the switch whenever a new cycle is detected
#LeetCode3650 #LeetCode #MinimumCostPathWithEdgeReversals #Java #JavaDSA #Graph #ShortestPath #Dijkstra #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
In today’s video, we solve LeetCode 3650 - Minimum Cost Path with Edge Reversals using Graph and Dijkstra's Algorithm in Java.
We are given a directed weighted graph with n nodes and need to find the minimum cost to travel from node 0 to node n - 1. We have a special switch at each node that allows us to reverse an incoming edge into an outgoing edge at double its original weight. Because all edge weights are strictly positive, any shortest path in the graph is simple and will never visit any node more than once. This means the constraint of using each node's switch at most once is naturally satisfied on any optimal path.
We model this problem elegantly by constructing an augmented graph where each original directed edge from u to v with weight w is accompanied by a virtual reverse edge from v to u with weight 2w. We then run standard Dijkstra's algorithm using a min-heap priority queue from source node 0 to target node n - 1. The algorithm gracefully handles unreachable destinations by returning -1 and runs in optimal O((V + E) log V) time with O(V + E) auxiliary space.
🔥 Problem Highlights
✅ Reversing an incoming edge from u to v into an edge from v to u costs twice the original weight
✅ All weights are strictly positive, guaranteeing that optimal paths are simple paths
✅ Augmented graph approach with virtual reverse edges eliminates state explosion
✅ Min-heap priority queue Dijkstra guarantees minimal cost exploration
✅ Handles disconnected graphs and multiple edges between nodes cleanly
✅ Time Complexity: O((V + E) log V)
✅ Auxiliary Space Complexity: O(V + E)
⏱️ TIMESTAMPS
00:00 Intro
00:58 Problem Understanding
02:28 Key Observation
03:30 Augmented Graph and Dijkstra Approach
04:45 Java Code Walkthrough
06:02 Execution and Test Cases
07:55 Time Complexity Analysis
08:44 Space Complexity Analysis
09:24 Outro and Wrap-up
📂 Problem Folder and Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals
☕ Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/Solution.java
🐍 Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.py
⚡ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.cpp
🌐 JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/January/27-January/3650-Minimum-Cost-Path-with-Edge-Reversals/solution.js
🔗 LeetCode Source Code
📌 Admin type the link
🌐 All LeetCode Solutions
📌 https://codebytushu.com/Leetcode/
📱 Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
❤️ Donate
📌 https://codebytushu.com/Leetcode/donate.php
🔥 Perfect For
LeetCode Medium Problems
Java DSA Preparation
Graph Shortest Path
Dijkstra's Algorithm
Augmented Graph Pattern
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
🌐 Follow CodeByTushu
▶️ YouTube: https://www.youtube.com/@codebytushu
📸 Instagram: https://instagram.com/codebytushu/
💼 LinkedIn: https://www.linkedin.com/company/codebytushu/
🌍 Website: https://codebytushu.com
🐙 GitHub: https://github.com/CodeByTushu
❤️ Don’t Forget To
👍 Like | 💬 Comment | 🔔 Subscribe
💬 Question of the Day
Why does adding reverse edges with weight twice the original weight not violate the at most once per node switch constraint in Dijkstra's algorithm?
1️⃣ Dijkstra keeps track of a bitmask of used switches for every vertex
2️⃣ All edge weights are positive, so the shortest path is always simple and visits each node at most once
3️⃣ Reverse edges can only be traversed during the first step of Dijkstra
4️⃣ The algorithm resets the switch whenever a new cycle is detected
#LeetCode3650 #LeetCode #MinimumCostPathWithEdgeReversals #Java #JavaDSA #Graph #ShortestPath #Dijkstra #DSA #CodingInterview #ProblemSolving #LeetCodeMedium #DailyLeetCode #JavaProgramming #CodeByTushu
👇 Comment the answer below! 🔥 Close description
