Chapter 22: Single-Source Shortest Paths: Bellman-Ford and Dijkstra's Algorithm

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Okay so think about this for a second.

You're in your car.

You need to get somewhere.

You pull out your phone, you tap on your GPS, and boom, you're trusting that little blue line to guide you the absolute fastest way possible.

Well today we're going deep into the brains behind that.

We're diving into the concept of finding the single source shortest path.

Now don't let the jargon scare you off.

This is actually a really neat piece of computer science and it's not just GPS.

This logic powers all sorts of systems.

Think about optimizing networks or scheduling those mega projects.

Yeah it's incredible how widely applicable this concept is.

Totally.

And I think what's fascinating for me is that the result we experience seems so simple.

Like the fastest route, you know?

But under the hood it's a really intricate dance of algorithms and calculations.

And that's exactly what we're going to unpack today.

Yeah let's do it.

We're going to keep it super clear and jargon free so you don't need a PhD in computer science to follow along.

For sure.

Think of this deep dive as your cheat sheet to understanding this core concept.

Yep.

Shortcut.

We'll break it down step by step starting with what the problem actually is.

Right.

The foundation.

Then we'll look at some of the different flavors of this problem.

Different ways it can manifest.

Exactly.

And we'll touch on the core ideas that make solving this whole thing possible.

The guiding principles.

After that we'll walk through three key algorithms.

Bellman -Ford.

Classic.

Dagshortest Paths.

And Dijkstra's.

The heavy hitters.

And to make it really real world we'll even see how this seemingly abstract problem shows up in something as practical as dealing with constraints.

Oh yeah that's a good one.

Our mission today is to give you the most important insights from all of this.

By the end you'll walk away feeling genuinely in the know about this crucial part of graph theory.

You'll be able to impress your friends at parties.

So to kick things off let's get back to basics.

What exactly are we trying to crack here?

Okay so we're dealing with what's called a weighted directed graph.

Okay a graph.

A graph right.

So like a network of things.

Yeah exactly.

Imagine points on a map.

Like little dots.

Yeah dots connected by lines.

Those are our vertices and edges.

Vertices are the dots.

Dots and edges are the lines.

Okay got it.

Now directed means these connections only go one way.

So like a one way street.

Exactly.

You can go from A to B but not necessarily back.

I'll catch it.

And then weighted.

This means each of these edges has a cost associated with it.

Like a toll booth?

Sort of it could be distance.

Okay.

Travel time or even like a financial cost.

So in our GPS example the weight is the time it takes to travel that road.

Yeah that's a perfect example.

Makes sense.

So we're trying to minimize this weight.

We want the shortest path.

The cheapest.

The fastest.

Tolls.

Exactly the most efficient route.

Okay and we want to find this from one specific starting point.

Right we call that the source.

Like our current location in the GPS to every other point on the map.

To all the destinations we might want to reach.

Got it.

And to be precise when we talk about the weight of a path we're simply talking about adding up all those weights along the edges you travel.

Like the total time for the whole trip.

Exactly.

So is there like a fancy way to write that?

There is.

We use a Greek letter delta.

Ah fancy.

So delta of U comma V.

Those are our start and end points.

Delta just represents the shortest distance between those two points.

Got it.

And of course sometimes there's no path between two points.

Like a road closure.

Yeah or just no road at all.

In that case the shortest path is considered infinity.

Infinity because you can't get there.

You literally can't get there so the distance is infinite.

Okay that makes sense.

And then a shortest path itself is simply any path that achieves that minimum weight.

So if there are multiple routes that all take the same amount of time they're all shortest paths.

They're all equally good in our eyes.

Cool.

And we might be thinking why not just try every single path.

Yeah just brute force it.

That's the brute force approach.

See which one is the smallest.

You could but trust me it's a computational nightmare.

Really?

Especially as our graph grows.

So more points more roads.

More points more roads more possibilities to check.

Like trying every route across the US.

Yeah exactly.

The number of possible paths explodes.

It's brute force is out.

Brute force is not going to cut it.

Okay so that brings us to the different versions of this shortest path problem.

You mentioned there were a few.

Yeah so we're focused on single source.

One starting point to everywhere.

Right but there's also single destination.

Okay so one ending point from everywhere.

You got it.

Interesting.

And think about it you can actually solve single destination using single source.

Oh really?

You just reverse everything.

All the directions in your graph.

Oh like flip all the arrows.

Exactly and make all the one way streets go the other way.

Then you run your single source algorithm from your original destination.

So you start at the end.

Yep and the shortest paths you find in this reversed graph they tell you the shortest paths back to that original destination.

So finding the best way to somewhere is like finding the best way from everywhere else just in reverse.

That's the gist of it.

That's pretty cool.

It's a neat trick.

What if I only care about the path between two specific points.

Ah that's single pair shortest path.

Okay.

Like from your house to work.

Exactly.

And the good news is if you solve the single source starting from your house you already have the answer for your commute.

Because it finds the shortest path to every point.

Including your office.

So single source actually solves single pair too.

It does.

Nice.

And then there's one more type.

You mentioned it earlier.

All pairs shortest paths.

What's that?

That's finding the shortest path between every single pair of points.

Whoa.

That's a lot of paths.

It is a lot more complex.

Probably a whole other deep dive.

We'll save that for another time.

Okay.

So we're laser focused on single source today.

Single source all the way.

Now you used a term earlier optimal substructure.

What's that all about?

Okay.

So this is a key property.

Okay.

Lots of efficient algorithms rely on this.

Including the ones we're going to talk about.

Yep.

Absolutely.

Okay.

So imagine you have the absolute shortest path between two points A and C.

Okay.

A to C.

And this path goes through a point B in the middle.

Okay.

Was like a pit stop.

Yeah.

Okay.

Optimal substructure says that the part of the path from A to B, that has to be the shortest path from A to B.

And B to C is the shortest path from B to C.

Exactly.

So if the fastest route from New York to LA goes through Chicago.

Okay.

The New York to Chicago part is the fastest way to get to Chicago.

Precisely.

You can't find a faster way to get to Chicago.

Interesting.

It just wouldn't make sense.

Yeah.

If there was a faster way.

You can use that faster way and make your New York to LA trip even faster.

Which wouldn't make the original path the shortest.

Exactly.

It would contradict our assumption.

Okay.

So why is this optimal substructure thing so important?

Well, it tells us we can build up our solution.

Okay.

By finding solutions to smaller parts of the problem.

Like little puzzles that fit together.

Yeah, exactly.

And this is the heart of dynamic programming.

Okay.

Where you break down a big problem into manageable chunks.

Solve the chunks then combine them.

You got it.

So we can find the shortest paths to nearby points.

And use that to figure out the shortest paths to further away points.

Precisely.

Got it.

Now things can get a bit tricky.

I don't know.

When we have edges with negative weights.

Negative weights.

Negative weights.

That sounds weird.

It is a bit unusual.

Or negative distance.

Yeah.

And the real world distances are always positive.

Right.

But in some abstract graphs, it can make sense.

Okay.

And it throws a wrench into things.

How so?

Well, the key is whether there are negative weight cycles.

Cycles like loops.

Loops in the graph.

Okay.

And if you go around that loop, the total weight you get is negative.

So you're gaining something by going in a circle.

Yeah.

It's like a loophole where you keep getting faster or cheaper.

Okay.

That does sound tricky.

It is.

So what happens then?

Well, if there are no negative cycles reachable from your starting point,

then even if some individual edges have negative weights,

the shortest path weights will still be well defined.

So they might be negative?

They could be negative.

But they still exist.

They still have a specific value.

Okay.

I'm following.

But if there is a negative weight cycle reachable from your source.

Then what?

Well, then the whole idea of a shortest path kind of breaks down.

How so?

Imagine you find a path to a place, but then you realize you can go around this negative cycle forever.

Oh, no.

Each time making the total path weight smaller and smaller.

So it's like a cheat code.

It is.

You could keep going around and around.

And the path gets shorter and shorter.

Technically, the path weight becomes infinitely negative.

Oh, wow.

So there's no shortest path.

There isn't.

It's undefined.

I see.

No, there's a figure in the material that illustrates this.

Okay.

It's helpful to see it visually.

Even though we can't see it, what would it show?

Well, it would likely show a graph.

Okay.

With maybe an edge having a negative weight or a loop where the weights add up to a negative value.

Okay.

And it would show how this messes up the shortest path calculations.

So it's like a visual aid to help us understand.

Exactly.

Okay.

So negative weight cycles are bad news.

They are bad news.

What about positive weight cycles?

Well, let's think about that.

Okay.

If you have a shortest path and it has a positive weight cycle,

you could remove that cycle and your path would be shorter, which means your original path wasn't actually the shortest.

So shortest paths can't have positive weight cycles.

Exactly.

It's a contradiction.

What about zero weight cycles?

They could technically exist, but they don't really add anything.

We can ignore them.

We can remove them and still have a shortest path.

So for simplicity, shortest paths don't have cycles.

Exactly.

And this leads to a really important point.

Yes.

About the maximum number of edges in a shortest path.

Right.

What is it?

So in a graph with V vertices, a shortest path can have at most V minus 1 edges.

Why is that?

Well, to form a cycle, you have to visit a vertex more than once.

Right.

You got to go back to where you were.

Exactly.

So if you have more than V minus 1 edges, you must have revisited a vertex.

Which means there's a cycle.

You got it.

And we know shortest paths don't have cycles.

Exactly.

So that limits the number of edges.

Okay.

So that's a key insight.

It is.

It helps us understand how some algorithms work.

Like Bellman -Ford?

Yep.

Bellman -Ford relies on this.

Okay.

So how do we keep track of these shortest paths?

Ah, that's where the predecessor subgraph comes in.

Okay.

Predecessor subgraph.

It's like leaving breadcrumbs.

Okay.

So for each vertex, we have a predecessor attribute.

Like who came before.

Yeah, exactly.

Okay.

So if we know the predecessor of a vertex, we can trace our steps back to the starting point.

Like following the breadcrumbs.

Precisely.

Cool.

And this predecessor subgraph ideally forms a shortest paths tree.

A tree?

It's like a branching structure.

Okay.

Rooted at our source vertex.

And this tree contains a shortest path to every reachable vertex.

Yep.

It's a nicely organized way to represent all the shortest paths.

Okay.

That makes sense.

Now let's talk about how we actually find these paths.

Yeah, the actual process.

This is where relaxation comes in.

Relaxation.

Relaxation.

Sounds nice.

It's a key operation.

Okay.

It helps us improve our estimates of the shortest pathways.

Estimates, so we're guessing.

We start with guesses and refine them.

Okay.

So for each vertex, we keep track of a shortest path estimate.

Like a placeholder.

Yeah.

And this estimate is always greater than or equal to the actual shortest pathway.

So it's an upper bound.

Exactly.

Initially, we set everything to infinity.

Infinity because we don't know how to get there yet.

Exactly.

Except for the starting point itself, that one we set to zero.

Because the distance from the start to itself is zero.

Makes sense, right?

Yep.

And we also set all the predecessors to null.

Null meaning nothing came before.

Right.

Because we haven't found any paths yet.

So everything's blank?

Fresh start.

Okay.

Now the relax procedure, it takes an edge.

Okay.

Like a connection between two points.

Okay.

And it checks if we can find a shorter path by going through the first point.

So it's asking, is it faster to go through this intermediate point?

Yeah, exactly.

Okay.

And if it is, we update our estimate.

For the second point?

For the second point.

Got it.

And we also update the predecessor.

To show that we reached that point through the first point.

Exactly.

We're leaving those breadcrumbs.

Okay.

So different algorithms relax edges in different ways.

Exactly.

They have their own strategies.

Okay.

So now let's dive into the first algorithm.

Okay.

Bellman -Ford.

This is a classic.

What's special about it?

Well, it can handle negative weights.

Ah.

So it can deal with those tricky scenarios.

It can.

And it can also detect negative weight cycles.

Which is super important.

Super important because those cycles can break things.

So how does it work?

It's pretty simple actually.

Okay.

It repeatedly goes through all the edges.

Okay.

And relaxes each one.

Right.

It does this V minus one times.

V minus one.

Why that number?

Remember we talked about the maximum number of edges in a shortest path?

V minus one edges.

Yep.

So by doing this V minus one times, we guarantee that we'll find the shortest path.

If it exists.

If it exists and it doesn't have cycles.

Okay.

Each iteration, we might extend our shortest path by one more edge.

Okay.

And after V minus one iterations, we've considered all possible paths.

That makes sense.

And there's a lemma that proves this.

Lemma like a mini -theorem.

Yeah.

It basically says, if there are no negative cycles after V minus one iterations, we found the true shortest path.

For every vertex.

For every reachable vertex.

Okay.

So that's how it handles negative weights.

Yep.

What about detecting those negative cycles?

Right.

So after those V minus one iterations,

it does one final check.

Okay.

It goes through all the edges again.

Okay.

And if it can still relax an edge.

Meaning it found a shorter path?

Yep.

That means there's a negative cycle.

Ah.

Because if there weren't, we'd be done.

Exactly.

Because that final check is like the alarm bell.

It tells us something's wrong.

Okay.

So what's the catch with Bellman -Ford?

Well, it's not the fastest algorithm.

Right.

Its running time is OV times E.

V times E.

V is the number of vertices.

Okay.

E is the number of edges.

So if there are a lot of edges, it gets slow.

It can get slow.

But it's reliable.

It's reliable.

It handles those tough cases.

So Bellman -Ford is our go -to for negative weights.

It is.

Now what about a special kind of graph called a DAG?

Ah, directed acyclic graph.

Acyclic meaning no cycle.

No cycles whatsoever.

So no negative weight cycles to worry about.

Exactly.

So things are simpler.

Much simpler.

Okay.

Tell me more about DAGs.

Okay.

So in a DAG, we can use a cool trick called topological sorting.

Topological sorting.

It means we arrange the vertices in a specific order.

Okay.

So that for every edge, the starting vertex comes before the ending vertex.

In the list.

In the list.

So it's like a hierarchy.

Kind of.

It gives us a clear path to follow.

Okay.

And the DAG shortest paths algorithm uses this.

How?

Well first it does the topological sort.

Okay.

Then it initializes the shortest path estimates.

Just like before?

Yep.

Same initial setup.

Okay.

But then it goes through the vertices in the topological order.

In that special order.

Exactly.

Okay.

And for each vertex, it relaxes its outgoing edges.

So the edge is going out from that vertex.

Precisely.

Okay.

And because of the topological order, we know we've already processed everything that comes before.

So we've already found the shortest path to those vertices.

Exactly.

Okay.

So when we relax the outgoing edges,

we're updating the shortest path estimates for the vertices that come after.

I see.

So it's all about the order.

The order is key.

And this works because of the topological sort.

Precisely.

And there's a theorem that proves this works.

Theorem 22 .5.

Okay.

So it's mathematically sound.

It is.

What about the running time for DAG's shortest paths?

It's much faster than Bellman -Ford.

Okay.

How much faster?

It's linear O of V plus E.

So it scales really well.

It does.

That's awesome.

Now you mentioned an application in Pert chart analysis.

Yeah.

Tell me more about that.

So Pert charts are used in project management.

Okay.

They show all the tasks in a project and how they depend on each other.

And the edges represent the tasks.

Okay.

And the weights represent the time it takes to complete each task.

Okay.

Now a critical problem is finding the critical path.

Critical path.

It's the longest path through the Pert chart.

Okay.

And this tells us the minimum time to finish the whole project.

So it's like the bottleneck.

Exactly.

Right.

And we can find this critical path using a shortest path algorithm.

Really?

We just flip the signs of all the weights.

Make them negative.

Yep.

And then the shortest path becomes the longest path.

You got it.

That's so clever.

It's a cool trick.

So we can use DAG's shortest paths to find critical paths.

Yep.

That's a real world application.

It is.

Now let's talk about Dijkstra's algorithm.

Dijkstra's?

This is a famous one.

It is.

It's very efficient.

Okay.

But it has one condition.

Okay.

All the edge weights have to be non -negative.

No negative weights allowed.

No negative weights.

All our costs are positive.

Or zero.

Okay.

So how does Dijkstra's work?

So it maintains a set of vertices for which we've already found the shortest paths.

So we're keeping track of what we've solved.

Exactly.

And in each step,

it ticks the vertex with the smallest shortest path estimate.

From the vertices we haven't solved yet.

Right.

So it's like a greedy approach.

It is.

We're always picking the closest one.

Okay.

And the reason this works is that once we pick a vertex with the smallest estimate, we know we've found its true shortest path.

Why is that?

Because all the other paths have to go through vertices with larger estimates.

Ah.

And since the weights are positive.

Non -negative.

And its paths can only get longer.

Exactly.

So Dijkstra's is like a smart explorer.

It is.

It always picks the most promising path.

Cool.

Now it uses a min priority queue to help with this.

A priority queue.

It's a data structure.

Okay.

It keeps track of the vertices and their estimates.

And it lets us efficiently find the vertex with the smallest estimate.

Exactly.

Okay, so the priority queue is important for speed.

It is.

What's the running time for Dijkstra's?

It depends on how the priority queue is implemented.

Okay.

If it's a simple array, it's O of V squared plus E.

V squared plus E.

If it's a binary heap, it's O of V plus E log V.

Okay.

And with a Fibonacci heap, it's even faster.

So the data structure matters.

It does.

You mentioned Dijkstra's is related to other algorithms.

It is.

Like BFS.

Bleth -first search.

So BFS is like Dijkstra's for unweighted graphs.

So when all the edges have the same weight.

Okay.

And Dijkstra's is also similar to Prim's algorithm.

Prim's algorithm.

It's used to find the minimum spanning tree.

Okay.

Both algorithms are greedy, but they have different goals.

Right.

Dijkstra's finds shortest paths from a single source.

Prim's finds the minimum spanning tree.

Exactly.

Okay.

So they're like cousins.

They are.

Cool.

Now you mentioned an application with difference constraints.

Yes.

This is a really neat one.

What are difference constraints?

They're a set of inequalities.

Okay.

Like math equations.

Yeah.

They look like X, J, minus G less than or equal to beaks.

Okay.

Where X, J, and G are variables and beak is a constant.

So like a system of equations?

Kind of.

And we can represent these as a graph.

A graph.

A graph.

So each variable becomes a vertex.

Okay.

And each inequality becomes an edge.

Okay.

And the weight of the edge is the constant beak.

Interesting.

We also add a new source vertex.

Okay.

And connect it to all the other vertices with edges of weight zero.

Okay.

Why do we do that?

It helps us with the shortest path calculations.

Okay.

Now there's a theorem that connects all this.

A theorem.

It says that the system of inequalities has a solution.

Okay.

If and only if the graph doesn't have negative weight cycles.

So we're back to negative cycles.

We are.

Okay.

And if there are no negative cycles.

Then what?

The shortest path distances from the new source vertex give us a solution to the system of inequalities.

So we can use Bellman -Ford to find a solution?

I agree, man.

Wow, that's amazing.

It is.

So shortest paths can solve math problems.

They can.

That's so cool.

Now the chapter also provides formal proofs for all of this.

Proofs?

Mathematical proofs.

Okay.

They show why all these algorithms work.

So it's not just hand -waving?

No.

It's rigorous math.

Okay.

They prove things like the triangle inequality.

Triangle inequality.

It's a basic property of shortest paths.

Okay.

They also prove properties about the shortest path estimates and how they converge to the true shortest path weights.

So the proofs show why all this works.

Exactly.

They provide the foundation.

Cool.

And you mentioned a glossary too.

Yes.

What's in the glossary?

It defines all the key terms we've talked about.

Okay.

So we've talked about things like weighted directed graph,

shortest path weight.

Shortest path.

Relaxation.

Negative weight cycle.

Coplogical.

Shortest.

Dykstra's algorithm.

All the important concepts.

So it's like a reference guide.

It is.

Awesome.

So to sum up.

Yes.

We've covered a lot of ground today.

We have.

We explored single source shortest paths,

different variations of the problem.

Vagative weights.

Optimal substructure.

Three key algorithms.

Bellman -Reford.

DAG shortest paths.

Dykstra's.

And even an application to solving inequalities.

It's amazing how versatile these concepts are.

It really is.

And it all comes down to this fundamental problem.

Finding the shortest path.

From one point to another.

In a weighted directed graph.

It seems simple.

But it's so powerful.

And it's the foundation for so much of modern technology.

Absolutely.

And it makes you think.

What else can we solve with these ideas?

Exactly.

What other unexpected applications are out there?

It's exciting to think about.

And with that, we've covered everything from this chapter on single source shortest paths.

We've done a complete deep dive.

All the major points, the theories, the findings, the examples.

Everything.

Thanks for joining us on this journey into the heart of graph theory.

It's been a pleasure.

Until next time,

happy pathfinding.

Happy pathfinding.