All language subtitles for 27 - Greedy Algorithm for Shortest Path Problem English

In this episode we're going to talk about greedy algorithms sometimes when they can be good and other

times when they can be bad in terms of mapping applications.

And so the problem that we're going to work with is a mapping application where we have a star here

and then in the first problem where we have an end here now a greedy over to them remember it always

takes the optimal path first.

So if you're looking for the shortest path it's going to take the shortest path over and over and over

again.

So if we created a path that looked something like this

then we're taking step one then turning step two and going up first three the side for four or five

side for six.

All the way until we get to the end.

And in this case the greedy algorithm would work.

And if you think you can this is something that gets proposed in a lot of quizzes and different algorithm

exams is asking if the shortest path.

If they agree on a that works with the shortest path and your first inclination may be to say yes if

you're creating a mapping application taking the shortest path over and over and over again does seem

like the smart way.

How ever there is a lot of different cases where this would actually be a horrible idea.

And I'll show you one of the best examples I've seen for it.

And so we're going to say the start is right here and we're going to put the end here so you can think

of these two different points on the map and we'll draw out some different roads.

So we're going to draw out roads that go something like this.

So that's one road.

And obviously because this is the shortest path we would take this one first then go and then keep on

going because the greedy algorithm would always take the shortest path first.

However in this case if there was a road that went straight right here to the end this would actually

be the optimal path.

This would be the way to go agree the algorithm though would not even consider this an option because

it would see the distance here as being greater than the distance right here.

And so it would always choose this option.

And so your greedy algorithm would actually go all the way around in order to get to the end.

And so in this case the greedy algorithm would be a very poor choice.

And this is something I've seen on different exams for analysis of algorithm problems and it's something

that I initially got wrong and was able to learn from it.

So make sure whenever you're asked this question you really think it all the way through and realize

that you know you need to know your data sources and you need to also think of some of the worst case

scenarios in order to know when a greedy algorithm can work and when it can.