
Title:
FloydWarshall Intro  Intro to Algorithms

Description:

I'm going to talk about an algorithm called Floyd Warshall

after two of the inventors of this algorithm back in the early 60s,

and it uses an idea called dynamic programming, which sounds so much cooler than its actually is.

That means, it actually is a very cool idea.

I have a professor friend who believes that I am predispose

to see all problems at dynamic programming problems because it an algorithm design technique

that I have been able to use successfully in a bunch of occasion,

but it really is just an algorithm design technique.

Its not particularly dynamic and it doesn't really change the way you think about programming.

It just have to do with optimizing using tables. Alright.

Let me start up by explaining this algorithm in terms of simple but possibly strange idea.

First just for simplicity, let's imagine all the nodes in our graph are numbered from 0 to n1,

and lots of graph have exactly have their structure, but for example for our marvel data set,

we have to all our characters be assigned numbers from 0 to n1,

but that's an easy thing to do, let's imagine that's already been done.

What we're going to imagine now is that someone has given us matrix.

Square matrix D of k and the entries of this matrix, just a big table like a spread sheet

and is filled in with values as follows.

The ij element of the i row, j column is filled in with the number

and that number is the length of the shortest path from i to j

hopping only all nodes numbered less than k.

So I don't know about you but I used to play a game like this when I was younger,

if I was in a building where the tiles were different colors, I'd sometimes declare

let's say, the blue tiles are alligators, so I'm not going to step on any of the blue tiles

and I'd try to walk stepping only on the tiles that I was allowed to use,

so that the analogue of this in the graph is imagine we've got our graph,

and we're trying to get a path from i to j, and some of the nodes are colored pink.

Those are the okay nodes because they are numbered less than k and some of the nodes

maybe including j itself are numbered higher than k, and we're not allowed to step on those.

We're trying to get from i to j, we're allowed to step on j opposite

but only the intermediate nodes that are pink.

We only consider making paths along pink nodes and there's only one in this case.

But there's some pink nodes that we don't use and their maybe multiple different pink paths,

but we want to know the distance of the shortest path using only the pink nodes.

Only the ones that are numbered less than k.

So let's imagine, some very hopefully, has done this for us and filled in the matrix with all those values.

There's big Î of nÂ˛ values that have to get filled in, but someone has does that for us. That's all great.

Our mission should we choose to accept it. Is to fill in Dk + 1.

So this will be a new matrix just like the old matrix,

but now when your going on a path from i to j, you're allowed to use node k.

You don't have to use it but your allowed so that's all we have to do right now.

Let's try to figure out if someone gives use Dk, how do we figure out Dk+1.