Shortest Path Algorithms Explained (Dijkstra's & Bellman-Ford)

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 79

  • @MoeSalamaIbrahim
    @MoeSalamaIbrahim 6 місяців тому +102

    Throughout this year's courses in my master's degree in electrical engineering, I've encountered Dijkstra's algorithm in almost all of my courses. I've never ceased to keep searching for explanations and perspectives of it, given my non-CS background but the sheer number of applications to this algorithm. Also, this year has made your channel one of my most enjoyable sources of informative relief. Thank you sir.

    • @CraftingCake
      @CraftingCake 6 місяців тому +2

      What specialty did you do in your masters?
      I have a bachelor in electrical engineering and we never talked about algorithms at all.
      I would even say, this is what differentiates me the most compared to computer science students.

  • @landchannel7688
    @landchannel7688 6 місяців тому +55

    10:25
    Ok but the idea of an electric car just going in circles between charging stations, hogging up more and more charge is genuinely funny.

  • @Blaze_0101
    @Blaze_0101 6 місяців тому +30

    00:01 Finding the shortest, optimized path is crucial in daily life.
    01:32 Dijkstra's algorithm is a key solution method for finding shortest paths.
    03:01 Using Min Heap priority queue to find shortest paths efficiently
    04:48 Dijkstra's algorithm finds the shortest path
    06:36 Dijkstra's algorithm cannot handle negative weighted edges
    08:22 Finding shortest paths using relaxation technique.
    10:08 The Bellman Ford algorithm can identify negative weight cycles in a graph.
    11:42 Negative weight cycle problem is an ongoing area of research.
    Crafted by AI ?

    • @bayunirayudha
      @bayunirayudha 6 місяців тому

      : : gajah mada
      #poxi
      #coin
      #boxi
      #asia
      #osis
      #intel
      #sony
      #linux
      sumarecone : :
      europe_negara@keraton

  • @DeokbaeKwak
    @DeokbaeKwak 6 місяців тому +14

    Best video to watch 3 days before my data structure exam

    • @deependrakumar5239
      @deependrakumar5239 6 місяців тому +3

      Bro this is algorithm not data structure 😂

    • @DeokbaeKwak
      @DeokbaeKwak 6 місяців тому

      @@deependrakumar5239 My lecture covers graph search algorithms 🙂‍↔️

    • @DeokbaeKwak
      @DeokbaeKwak 6 місяців тому +1

      @@deependrakumar5239 It includes search algorithms related with various data structures bruh

    • @deependrakumar5239
      @deependrakumar5239 6 місяців тому

      I understand your feeling brother, but we use algorithm in data structure to make effective and scalable code.

    • @DeokbaeKwak
      @DeokbaeKwak 6 місяців тому +2

      @@deependrakumar5239 I get it. I just wanted to say that this video helped me understand the algorithm much better

  • @DIGITALPEPacksyCursos
    @DIGITALPEPacksyCursos 5 місяців тому +2

    7:46 Bellman-Ford

  • @dlv5652
    @dlv5652 6 місяців тому +3

    I was just thinking about this! Thank you

  • @arnav6237
    @arnav6237 Місяць тому

    Fantastic video, great explanation and visuals.

  • @robinsonrojaslopez5200
    @robinsonrojaslopez5200 6 місяців тому +1

    I don't know much about how the algorithm works, but if you are looking for the smallest value, I understand that it cannot be less than zero since this way you would avoid the problem of entering a cycle in which the value is decreased. infinitely, to prevent the value from being less than zero you can look at what the weights are and look for the smallest one, in the first example -30, and add the absolute weight in the rest in this way this node (and the others with existing negative values) has a value equal to or greater than zero and the problem is avoided.

    • @Giovanni-rh1pw
      @Giovanni-rh1pw 14 днів тому

      Yeah but now whatever value you find has no meaningful interpretation

  • @chri-k
    @chri-k 6 місяців тому +1

    One thing: for Dijkstra's algorithm, if you're going to visit every node (so, if you have a small-ish graph), there's no reason to use a min heap

  • @jshet
    @jshet 6 місяців тому +1

    Was literally doing this chapter of Grokking Algorithms this morning.

  • @priyanshumaity6780
    @priyanshumaity6780 6 місяців тому +24

    I know that you probably have answered this question quite a lot of times, but if you don't mind can you please tell me what software you use to create these animations?

    • @vastabyss6496
      @vastabyss6496 6 місяців тому +1

      he probably uses PowerPoint like CoreDumped

    • @vastabyss6496
      @vastabyss6496 6 місяців тому

      and I'm not joking when I say that

    • @priyanshumaity6780
      @priyanshumaity6780 6 місяців тому +2

      @@vastabyss6496 When I think about it, it's not a bad idea. Thanks 🙏🏼

    • @chry003
      @chry003 6 місяців тому +2

      Or, manim!?

    • @vastabyss6496
      @vastabyss6496 6 місяців тому +6

      @@chry003 Manim and Motion Canvas are great, but I don't think that's what's being used here. If there was an algorithm being visualized that was doing tens or hundreds of operations, then using something like Manim would be best since it would be a pain to animate that all by hand. For this video though, it seems like animating it by hand wouldn't be too hard

  • @subinaypanda9936
    @subinaypanda9936 6 місяців тому +1

    A few days before I have hard time to understand bellman ford algorithm. I like how you have explained two algorithms in just 13 minutes.

  • @marvinchuakhaichien2361
    @marvinchuakhaichien2361 6 місяців тому +3

    Loved your videos and animation! Mind sharing what software you used to make all these animations? (hope it's not just After Effects 😂)

  • @TheGoldenPro
    @TheGoldenPro 6 місяців тому +5

    OMG he's alive!

  • @Leon-eu7od
    @Leon-eu7od 4 місяці тому

    Excellent explanation! Can I ask which software do you use to create this fantastic animation video? Thanks a lot!

  • @stdavid_
    @stdavid_ Місяць тому

    Very good video!

  • @Idan_Nesimov
    @Idan_Nesimov 6 місяців тому

    Great content young man !

  • @abderus4220
    @abderus4220 4 місяці тому

    Maybe I'm wrong but wouldn't that problem with negative numbers be solve if you prioritize nodes with no active predecessors instead of min values?

  • @jobygejo3322
    @jobygejo3322 6 місяців тому +1

    Finally you are back

  • @na50r24
    @na50r24 6 місяців тому

    Question:
    Dijkstra should work for any graph as long there is no negative weight, no? Being a DAG is not a requirement for Dijkstra.
    Not sure if this is a weird question but Dijkstra is greedy but happens to work. Isn't there a non greedy Dynamic Programming approach to the shortest path problem? The reason for the second question: I think DAGs are graphs that can be actually solved with topological sorting and DP but I could be wrong.

    • @b001
      @b001  6 місяців тому +1

      Correct, being a DAG is not a requirement for Dijkstra’s, nor is it a requirement for Bellman-Ford as long as the cycle isn’t negative and reachable by the source. I choose a DAG so that I could use the same graph throughout the video, so that once I created a negative weight edge, it ensured no negative weight cycle could exist so that the Bellman-Ford algorithm could solve it.

  • @realdlps
    @realdlps 2 місяці тому +6

    My genius fix for those negative loops is just assuming they don't exist...
    Take the largest (or well technically smallest) negative weight in the graph, then subtract that from all weights in the graph. Now the smallest weight is 0, and the problem is kind of "solved" and you can find a path. This probably has a lot of problems, but it does get you a solution, which many times is better than only being able to say that "yeah, there's a loop that breaks my algorithm"

    • @EE-ho1iz
      @EE-ho1iz Місяць тому

      There's someone else who asked about that in the comment already, and here's the problem with it (quoted from @asston712):
      that doesnt work. Say we have a graph with each edge bumped up by N distance. If we have a certain path that passes through 3 edges, the total bumped distance will be 3*N longer than the actual distance. However, consider a path that passes 5 edges, this path will have a total bumped distance 5*N longer than the actual distance. Bumping unfairly favors paths that travel over fewer edges. A concrete example is lets say we have 2 paths we can take: 1,1,1,1,1,1,1
      or 20, -10
      we know the top path is more efficient, but after bumping each distance by 10:
      11,11,11,11,11,11,11
      or 30,0
      the bottom path becomes for efficient

    • @RobinLogic
      @RobinLogic Місяць тому +1

      Wait, this could work. You are just shifting the baseline of the cost of each edge upwards. At the end you still attain a result, if we want to find the actual cost, could we not just add the original value of the smallest value from the total cost of the path? What are the potential issues?

    • @EE-ho1iz
      @EE-ho1iz Місяць тому

      There's a problem with this, explained by @ashton712 in the comments (credit to them!):
      that doesnt work. Say we have a graph with each edge bumped up by N distance. If we have a certain path that passes through 3 edges, the total bumped distance will be 3*N longer than the actual distance. However, consider a path that passes 5 edges, this path will have a total bumped distance 5*N longer than the actual distance. Bumping unfairly favors paths that travel over fewer edges. A concrete example is lets say we have 2 paths we can take: 1,1,1,1,1,1,1
      or 20, -10
      we know the top path is more efficient, but after bumping each distance by 10:
      11,11,11,11,11,11,11
      or 30,0
      the bottom path becomes for efficient

    • @gayfish2406
      @gayfish2406 Місяць тому

      @@RobinLogic paths with more nodes will get more additional costs

    • @jamesclarit1619
      @jamesclarit1619 11 днів тому

      Yea this doesnt work

  • @Pogoda450
    @Pogoda450 3 місяці тому

    Amazing video!!

  • @xiayunlong
    @xiayunlong Місяць тому

    Why in Dijkstra's method we hoard those pending vertex in a min-heap priority queue? Why can't we just using a normal queue to hoard those pending vertex like a bfs process?

    • @Giovanni-rh1pw
      @Giovanni-rh1pw 14 днів тому

      In a queue you're prioritizing those who got added there first. But there's no inherent value with doing so in a weighted graph. What actually matters is the total distance up until that node. This translates directly to the fact that, in Dijkstra's algorithm, once you pop a vertex off the priority queue, you've found the minimum distance. Because in a graph with non-negative edges the function total distance vs time run is monotonically increasing, so once you pop off some distance x, all the remaining distances are at least x, which means that's the shortest possible distance from some vertex. Therefore, you can mark it as visited and not go through it again

  • @Milenakos
    @Milenakos 6 місяців тому +1

    just bump all values by some amount such that the smallest negative becomes 0?

    • @asston712
      @asston712 6 місяців тому +4

      that doesnt work. Say we have a graph with each edge bumped up by N distance. If we have a certain path that passes through 3 edges, the total bumped distance will be 3*N longer than the actual distance. However, consider a path that passes 5 edges, this path will have a total bumped distance 5*N longer than the actual distance. Bumping unfairly favors paths that travel over fewer edges. A concrete example is lets say we have 2 paths we can take: 1,1,1,1,1,1,1
      or 20, -10
      we know the top path is more efficient, but after bumping each distance by 10:
      11,11,11,11,11,11,11
      or 30,0
      the bottom path becomes for efficient

  • @Jaiden-2013
    @Jaiden-2013 6 місяців тому

    Is this true:
    the most battery path is Bellman ford algorithm but set the starting location to “max battery” - “current battery” and disallow vertices to be negative

  • @asoawrahman9218
    @asoawrahman9218 6 місяців тому

    Great explanation, very understandable.
    A question: What software do you use for these animation, and illustration?

  • @guilhermeduarte1932
    @guilhermeduarte1932 6 місяців тому

    How do you know or find a way to determine the weight for each edge?

    • @DIGITALPEPacksyCursos
      @DIGITALPEPacksyCursos 5 місяців тому

      could be the lenght of a road, or as in this video the charge quantity. What I'm saying is that the edges weight have to be part of the previous data

  • @bordercollie0115
    @bordercollie0115 6 місяців тому

    I love theas vids so much i missed them ❤

  • @Med_Am_AB
    @Med_Am_AB 6 місяців тому

    Finally it's been a long time

  • @janaafifi1410
    @janaafifi1410 4 місяці тому +1

    you are a genius I hope you always have a cold side on ur pillow sir

  • @vader567
    @vader567 6 місяців тому +2

    thats why i fkin love cs

  • @keithmorgan6498
    @keithmorgan6498 4 місяці тому

    Perhaps too simplistic but if you have a path of -25 on one vertex add 26 to all paths so that every path is positive. Then you could use Dijkstra's algorithm. :)

  • @ransarawijitharathna7566
    @ransarawijitharathna7566 Місяць тому

    Thank you

  • @dipeshsamrawat7957
    @dipeshsamrawat7957 6 місяців тому

    Thank you 😊

  • @CultureofSpeech
    @CultureofSpeech 6 місяців тому

    Salute 🙌
    Bravo 👏👏 Lit 🌠 Impressive ❤ Gratitude 🥳✨ for your satisfactory Work 🚀🌟🌱

  • @fire17102
    @fire17102 6 місяців тому

    A* in python next please ❤

  • @jamescollier3
    @jamescollier3 6 місяців тому +1

    what about if some of these are highways

    • @Loaderdani
      @Loaderdani 6 місяців тому

      Then the weight of those edges will be less, assuming that the computer is using time and not distance as its cost function.

    • @Loaderdani
      @Loaderdani 6 місяців тому

      The algorithm doesn’t know the shape of the map, just the distance (in time) between intersections.

  • @1.0
    @1.0 6 місяців тому +12

    Duh, the shortest path is obviously a direct line between the points /j

  • @potatofuryy
    @potatofuryy 6 місяців тому

    A* My beloved

  • @PunamTish
    @PunamTish 5 місяців тому +1

    What's the meaning of your UA-cam channel's name !

    • @b001
      @b001  5 місяців тому

      Originally, it was b001ean, using boolean values 0s and 1. It was later just shortened to b001 (pronounced “bool”)

  • @KelvinWKiger
    @KelvinWKiger 6 місяців тому

    bravo

  • @MuhammadAlotaibi1324
    @MuhammadAlotaibi1324 6 місяців тому

    yet gives you the longest path

  • @iTz_Nao
    @iTz_Nao 6 місяців тому +1

    first

    • @michaelt312
      @michaelt312 6 місяців тому +1

      I'll take things that annoying to hear both on UA-cam and in bed for $100.