Bellman Ford Algorithm

This video explains the bellman ford algorithm which is also a single source shortest path algorithm just like dijkstra algorithm but the only difference is that, bellman ford algorithm can detect negative edge cycles which dijkstra cannot.The time complexity of bellman ford is higher than dijkstra and so bellman ford should only be used if we have chances of getting a negative edge weight cycle.In this video, I have explained briefly the difference between bellman ford and dijkstra algorithm and then i have explained how we can simply solve shortest path problem for undirected graph using dijkstra algorithm to solve it faster.I have also shown all the steps for bellman ford algorithm with intuition and reason behind performing each step.Finally i have shown how to detect a negative edge weight cycle. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL VIDEOS:-
Dijkstra algorithm: • Dijkstra algorithm | S...
Spanning Tree | MST : • Spanning Tree | MST | ...
Prims algorithm: • Prims algorithm | MST ...
Kruskals algorithm: • Kruskals algorithm | C...

[@amitsamui4008]

you are too good in explaining confusing stuffs. Great!!

[@techdose4u]

Thanks 😊

[@sivasubramani612]

Can you please tell which software you're using for this presentation. It could be helpful while I learn, teach and explain others

[@vijaykumarlokhande1607]

Undirectional graph with all edge +ve weight -> apply Dijkastra
Undirectional graph with at least one edge -ve weight -> Neither Dijkastra nor Bellman Ford.
Directional graph with -ve edge weight CYCLE -> Neither Dijkastra nor Bellman Ford works. but ford will inform us.
Directional graph with no -ve edge weight CYCLE, but with negative edge -> Bellman Ford works but what about dijkastra?

[@kumarpriyansh4238]

How do you know prior that your directed graph with -ve edge contains -ve edge weight cycle or not. if you know surely use dijkstra but if you dont, use Bellman Ford.

[@conor3087]

Exactly the same doubt I have now bro. Have you found out??

[@ojasdighe991]

any type of graph with negative edge weight leads to incorrect results if dijkstra is used.

[@SachinSingh-qf3wi]

Why v-1 iteration is needed this part is i unable to understand

[@RakibHasan-455]

Best Explaination ever man!! If you add it's code implementation link then it would be more great.

[@techdose4u]

Sure

[@sohamshinde1258]

*Thankyou* x ♾ 🙏🙏🙏🙏🙏 🙏🙏🙏

[@techdose4u]

Welcome 😊

[@sallaklamhayyen9876]

great explanation. thank you so much

[@sheldon9415]

Amazing explanation! Thank you, sir!

[@techdose4u]

Welcome :)

[@Ck-ir8ts]

This channel will go the distance.

[@techdose4u]

Thanks :)

[@kunalsoni7681]

Really amazing algorithm 😊🥰
Thank you so much for making kind of great videos always 😍🙂🥰😊

[@techdose4u]

Welcome bro :)

[@asifsaad5827]

To find the existence of negative cycle, do we need to run the algo twice or just run "V-1" times and another time to see if any change happens?

[@techdose4u]

V times only.

[@shivanisrivastava3219]

Nice Explanation!!

[@techdose4u]

Thanks :)

[@satvik_b]

awesome explanation

[@Vishnupraharshan2]

2:50 Dijkstra will not work for -ve edge weights rt? Since, in Dijkstra once the node it processed it will never revisit it again and there exists a possibility that in later stage a -ve weighted edge is connected to already processed node, with an impact to the shortest path of a processed node.

[@Luna-vk9xy]

Dijkstra's doesn't work if any -ve weight edges are present, regardless of whether it forms -ve weight cycles or not. Bellman ford can handle -ve weighted edges, but not -ve weighted cycles.

[@naman_goyal]

Nice explanation

[@techdose4u]

Thanks

[@priyanshvatsal9791]

Big thanks

[@divanshmahajan1769]

Can Dijkstra get shortest path for negative edges..?? Which don't form a cycle..

[@techdose4u]

Yep. You can try it. It should work because the problem is only with negative edge cycles. In that case, Dijkstra will give you wrong answer while bellmanFord will tell you that there won't be a negative edge cycle.

[@divanshmahajan1769]

@@techdose4u ok so bellman will tell us that negative weight cycle exists whereas ..Dijkstra will give a wrong ans but if negative edges are there not leading to cycle then Dijkstra will also work right??

[@AnilKumar-un1zo]

In some cases without cycle also it gives wrong ans.

[@shriharikulkarni3986]

Does dijkstra work on directed/undirected cyclic graph with non negative edge weights ?

[@devanshgoel9070]

thank u sir!

[@sujoyseal195]

Great ! Awesome 👍💯😊

[@techdose4u]

Thanks 😊

[@willturner3440]

Thank you boss

[@startsnehagarg]

the complexity of dijkstra using priority queue in java should be 0(v+elogv) .why are you take e0(elogv)?

[@neilchaudhary007]

Because ElogV is greater than v so O(v+ElogV) is as good as O(ElogV)

[@nguyenvankhanhduy3958]

Does Bellman Ford algorithm work on undirected graph too?

[@vijaykumarlokhande1607]

yes

[@kartikchechani2299]

@@vijaykumarlokhande1607 how it will go in infinite loop

[@sarthakrana5658]

Bellman Ford works on undirected graph only when all edge weights are positive. See @5:12

[@kmishy]

8:37 What rule you followed to write edge order on the right side of board?

[@kumarpriyansh4238]

Order doesn't matter. You can go in any order.

[@devashishpardesi1692]

BFS

[@visheshmittal468]

Sir basically Bellman Ford Algorithm is dijkstra algorithm repeated V-1 times?

[@kumarpriyansh4238]

Nope. They are fundamentally different. In dijkstra you traverse weight array to find minimum unvisited node. But in bellman ford..you go through all edge list irrespective of their weight . You just repeat it v-1 times without concerning about min value.

[@SujonKumarDey]

great, Thanks man

[@techdose4u]

Welcome :)

[@deepanshu6576]

why we relax v-1 times?edges

[@techdose4u]

We have to relax v-1 vertices and the last one will automatically get relaxed. I have explained in my videos in MST as well as in previous videos. If you don't understand any specific reason then do let me know

[@jithishvinovino405]

Confused

[@bhupeshpattanaik7150]

Code 😭

[@selvanambi9852]

Explain Tamil video

[@CriticRoshun]

Change the misleading thumbnail! 😠

[@techdose4u]

I used a different example. Wasn't that bellman ford ? Did you or I miss something ?

[@CriticRoshun]

@@techdose4u by looking at the thumbnail it seems you will be working with undirected graph and may be figuring out a minimum spanning tree or something. I too came for that spanning tree. But can't find any reference to the same. Does even Bellman Ford help you find MSP???

[@techdose4u]

You misunderstood. Bellmanford is for Shortest path. I have drawn the diagram for shortest path. If you don't know what this algo is then I can't blame myself for having made this thumbnail. It correctly depicts what I wanted to convey. But if you misunderstand then perhaps you should study bellmanford cause you don't know it. So, this video will teach you that :) Isn't that correct ?

[@CriticRoshun]

@@techdose4u thanks for making me "watch this entire video and NOT find the example graph mentioned in the thumbnail."
Thank you genius.

[@sudesh2714]

@@CriticRoshun just get rid of the thumbnail bro, he doesnt made any mistake, well explained!