- Okay, so here we are week 13 of CS124 online,
Data Structures and Algorithms.
And last week we wrapped up the dynamic equivalence problem.
We introduced graphs and we saw our first graph algorithm,
which was topological sort.
And this week we've got some really cool stuff.
So we'll see how to find the shortest paths in a graph.
So if we have some graph, with all these nodes and edges,
we're gonna be able to pick a particular node in that graph
and find the shortest path through the graph,
no matter how complex it is,
to all the other nodes in the graph.
And we're gonna do this using
what's called Dijkstra's algorithm,
one of the most famous algorithms in computer science.
And Dijkstra's algorithm uses a greedy approach
to find these paths.
And it works as long as there are no negative edge weights
in the graph.
So if we have a negative edge weight,
which is reasonable thing to have
in a number of different kinds of problems,
then Dijkstra's no longer works.
And so what we'll learn is to handle graphs
with negative weight edges but no negative weight cycles.
We'll use what's called the Bellman-Ford algorithm.
And the Bellman-Ford algorithm is very much like Dijkstra's
and so it makes sense to present the two together.
So we'll see they're very, very similar kinds of algorithms.
There's just a few differences.
And after exploring these shortest path algorithms,
we'll look at what are called network flows
where we have networks that are represented by these graphs.
And we wanna find the maximum flow
that can flow through the network from some node
that we designate as the source to some other node
that we designate as the sync.
And the weights, these are weighted directed graphs
that we'll be looking at and the weights in these graphs,
these networks, represents the capacity
that can flow along each edge.
So we're designating one node as the source,
one is the sync, and it turns out
that finding the maximum flow through a network like this
is equivalent to finding what's called
the minimum cut through the network,
and you'll hear the term max-flow min-cut.
And a cut is where we have some graph
and we remove a subset of the edges
so that we disconnect the graph
into two disconnected components.
So if we have the source and we have the sync,
a cut is where we remove a subset
of the edges in the connected graph in the network
to separate the source and the sync.
We're only concerned about cuts
that separate the source and the sync
into two, as elements in two disconnect components.
And whenever flow through a network,
whenever we have flow through a network,
it's gotta flow through at least some of those edges
in the cut in the graph, because of the sync's over here,
the source is over here,
and it's gotta go through some of those edges
that we removed to produce the cut.
So if we can find some cut in the network
with some sum of the weights of the edges,
which are the capacities,
we take the sum of the weights of the edges that we remove,
we certainly can't have flow through the network
that exceeds the value of such a cut.
So maximum flow and minimum cut are two sides
of the same coin.
The maximum flow through a network
is the same value as the minimum cut
that we can find through the same network
that separates the source from the sync.
And to solve the problem of finding the maximum flow,
we'll learn about the Ford-Fulkerson
and Edmonds-Karp algorithms.
And these also, like Dijkstra's and Bellman Ford,
take a greedy approach, finding the maximum flow
by iterating and finding what are called augmenting paths,
which is a path from the source to the sync
that still has some capacity on it.
And the flow supported by each augmenting path
is added to the solution in a greedy fashion,
until we can find no more augmenting paths in the network.
And once we do,
then that's supposedly gonna give us the the maximum flow.
But we'll see, there's a gotcha. There's a gotcha.
And it's possible to find
a bad sequence of augmenting paths,
but with a little trick
we'll show how we can resolve that problem.
And so that's Ford-Fulkerson and Edmonds Karp.
And I think the best way to learn these algorithms
is to actually work through some examples yourself
with pencil and paper.
So I'm gonna provide some problems for practice.
And the smart money says
that there will be problems like these on the final exam.
So we're definitely gonna touch on these algorithms
on the final exam.
So a little practice will be good preparation.
And then here's the part of the spiel
that's always the same every week.
At the end of the week we're gonna have another quiz
running from Thursday to Sunday.
It'll cover this week's material
and a little bit of material from what we covered last week.
So that's all for now
and I'll see you on our Yellowdig Discussion Board.
Bye bye.