Now in the context of a driving directions application

it's natural to ask the question why would you ever care about negative edge lengths.

Until we invent a time machine that doesn't seem like

negative edge lengths are going to be relevant when you are computing literal

paths through literal networks.

But again remember that paths can be thought of as more abstractly as a just

sequence of decisions.

And some of the most powerful applications of shortest paths

are coming up with optimal weight such sequences.

So, for example, maybe you're engaging in financial transactions and

you have the option of both buying and selling assets at different times.

If you sell then you get some kind of profit and

that would correspond to a negative edge length.

So there are quite interesting applications in which negative edge

lengths are relevant.

If you are dealing with such an application,

Dijkstra's algorithm is not the algorithm to use.

There's a different shortest path algorithm, a couple other ones.

But the most well-known one is called Bellman-Ford.

That's something based on dynamic programming,

which we may well cover in a SQL course.

Okay, so for Dijkstra's algorithm, we always focus on graphs.

That'll have only non-negative edge lengths.

So, with the next quiz, I just want to make sure that you understand the single

source shortest path problem.

Let me draw for you here a simple four node network, and ask you for,

what are the four shortest path lengths.

So from the source vertex s, to each of the four vertices in the network.

All right, so the answer to this quiz is the final option, 0,1,3,6.

To see why that's true, well,

all of the options had 0 as the shortest-path distance from s to itself.

So that just seemed kind of obvious.

So the empty path will get you from s to itself and have 0 length.

No suppose you wanted to get from S to V, well there's actually only one way to do

that, you have to go along this one hop path.

So the only path has length of one, so the shortest path distance from S to V is one.

Now W's more interesting, there's a direct one hop path, SW,

that has a length of four, but that is not the shortest path from S to

W Inf act to two-hop path that goes through v as an intermediary has

total path length three which is less than the length of the direct arc from s to w.

So therefore the shortest distance from s to w is going to be 3.

And finally for the vertex t there's three different paths going from s to t.

There's the two-hop path that goes through v.

There's the two hop path which goes through w, both of those have path length

7, and then there's the three hop path which goes through both v and w.

And that actually has a path length of one plus two plus three equals six.

So despite having a largest number of edges, the zigzag path is, in fact,

the shortest path from s to t and it has length 6.

All right, so before I tell you how Dijstrka's algorthin works,

I feel like I should justify the existence of this video a little bit.

All right?

Because this is not the first time we've seen shortest paths.

You might be thinking rightfully so.

We already know how to compute shortest paths.

That was one of the applications of breadth first search.