Concept Challenge: Performance of Dijkstra's Algorithm

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

880 ratings

University of California San Diego

Advanced Data Structures in Java

880 ratings

Course 3 of 5 in the Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

From the lesson

Finding shortest paths in weighted graphs

In the past two weeks, you've developed a strong understanding of how to design classes to represent a graph and how to use a graph to represent a map. In this week, you'll add a key feature of map data to our graph representation -- distances -- by adding weights to your edges to produce a "weighted graph". Although this might seem like a small change, the algorithms that work for unweighted graphs may prove ineffective for weighted graphs. To address this problem, you'll explore more advanced shortest path algorithms. First, you'll see how to find the shortest path on a weighted graph, then you'll see how to find it more quickly. In the project, you'll apply these ideas to create the core of any good mapping application: finding the shortest route from one location to another.

Core: Shortest Path with BFS3:28

Core: Geographic Maps4:12

Core: Dijkstra's Algorithm8:56

Concept Challenge: Performance of Dijkstra's Algorithm8:02

Core: A* Search Algorithm5:14

When I struggled: Tackling large programming projects1:26

When I Struggled: Remembering classical algorithms0:31

Meet the Instructors

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

[CROSSTALK] >> All right,

in this concept challenge, we're gonna look at Dijkstra's Algorithm.

And we're gonna do some runtime analysis.

So you'll need your big o skills out and ready for this concept challenge.

You know the drill.

I'm not gonna dwell on it.

You'll have a couple chances to answer the question.

And you'll get to see the UCSD learners discussing.

And you'll get to hear our explanation.

So here's your question.

Here's Dijkstra's algorithm as Leo presented it.

And the question we have for you is, what is the running time of this algorithm in

terms of the number of edges and the number of vertices in the graph?

>> Hi, my name is Wong.

>> Hi, I'm Miguel.

>> Hi, my name is Yu Mei.

>> So let's get started.

>> Okay.

>> For this question, I don't think the answer should be A or

E because durable is having score so long and it's too much.

>> Yeah, I definitely agree.

Just because it says for each of curr's neighbors n.

So that's saying like oh, it's the edges between curr and n.

>> Mm-hm. >> So we're working with the edges and

not the vertices.

>> Mm. >> I think the answer is C.

if you look at the while loop, he loops through every single edges.

And in sides of loop we're popping from the queue

which takes about off n and that n in this case is edge E, right?

>> That's a good guess.

But why don't we consider vertices which is D cuz C doesn't include V.

>> Why do we need to include vertices?

>> Mm, because that's talking about running time.

We have to go over the vertices.

>> Oh, we need to include vertices because we're adding

all the vertices to the [LAUGH] priority queue first.

>> Oh, that's right.

I forgot about initialization.

>> Now that you've watched the UCSD learners discuss the problem and

thought about it, let's go over the answer here.

So the way we solve a big o problem is of course we're just gonna trace to the code

and think about all the steps that need to be done and how long they take.

So let's start with the very first step.

This initialization step.

And if you think about the initialization, a lot of these steps are very fast but

there's one that's gonna take a little bit longer.

So what we have to do in the beginning is we have to set all of the distances

in our graph to infinity.

So we had to set that distance on every single node.

So it's going to take order the number of vertices or nodes in the graph.

So that's how long that first step is gonna take.

Then we go on to the next step in the graph and

we can see that that's a constant time operation.

So how do these two steps combine?

Let's just take a moment and pause and

think about how these first two steps combine before we move forward.

So whenever we have two steps that execute in sequence in an algorithm,

you do one after the other.

Then you're just gonna add together the running times to figure out

the total running time.

So at this point, we would have a running time of the sides,

the number of vertices in the graph plus 1.

But of course you know that o of the number of vertices in the graph plus 1

is just equal to o of the number of vertices in the graph so

we don't really need that plus 1 at all.

Consequently, we can kind of disregard this line that only took one

operation as well.

So we're just gonna omit that from our analysis for now as well as omit

explicitly counting any of the other lines that have just constant running time.

So let's continue.

Let's go down now, and now we're into the meat of the algorithm,

this while loop that's going to keep doing something,

keep doing stuff as long as the priority queue is not empty.

So this is a really big question.

How many times does this loop run?

Well, for a clue,

we need to figure out how many nodes go into this priority queue.

How many entries, not just nodes but how many entries?

Cuz as you remember, the entries are going to be nodes plus distances.

And the same node with a different distance is going to be a different entry

in this priority queue.

So let's look at where these entries get end queued.

It's down here, okay?

So what exactly are we doing down here?

Well if you look at where we are in the algorithm, we're in the for

loop that's going away from a particular node finding its neighbors.

And the neighbors are basically just the edges of a particular node.

So effectively what we're doing is we're adding one entry for

every edge in the graph.

Because for every node we're exploring out along all of its edges

to find the neighbors.

So each edge will lead to a new entry in that priority queue.

So that priority queue, that while loop then, is going to have running time

order the number of edges in the graph, okay?

So that's how many times this loop is going to run.

But now we need to take into consideration how long does each iteration

of the loop take in the worst case?

So now we're gonna go inside the loop.

And all of these costs are going to be multiplied

by the number of times the loop runs.

So most of these operations inside the loop have constant time.

So I've grayed out all the operations to have constant time.

So we can focus on the operations that may or

may not need to be considered explicitly.

So let's consider this first statement here.

Dequeuing the note from the front of the queue.

Well if you remember back to what Leo said about priority queues, dequeuing and

enqueuing nodes in a priority queue.

So if we go down here as well,

can be done in log(N) time where N is the size of the priority queue.

Well our priority queue could be, at worst, the number of edges in the graph.

So the time it could take to enqueue or dequeue from or

into that priority queue could be log of the number of edges in the graph.

So that's gonna be our running time bound for

these two steps of dequeuing and enqueuing into the priority queue.

So now we're left with this for loop statement.

And the question is, what should we do about it?

Do we need to somehow account for it?

Maybe multiply that enqueue operation by the number of times the for loop iterates?

Well, in fact, we don't because we've already counted for

this for loop's iterations where we talked about accounting for

the overall iterations of the while loop.

Because this for loop is basically just adding stuff to the priority queue.

And it's the while loop that's gonna keep running

while the priority queue is not empty.

That's going to basically govern

the total work that this part of the algorithm is doing.

So this for loop here has already been accounted for in our total number of

calculations of how many times this while loop is going to run.

So we can for now disregard it.

And then we get to the final answer here that the while loop in total,

taking into account what it does in it's body,

takes the number of edges times log of the number of edges.

Putting that together with the first step of the initialization step,

we get to that the total running time is order number of edges

times log of number of edges plus the number of vertices in the graph.

Now that's a fine answer but if you go look online,

you might find that the answer is slightly different from what we just derived here.

You'll probably see an answer that looks like the statement here at the bottom.

That the running time is order of the number of edges times

logarithm of vertices plus the number of vertices.

So what just happened?

How did we go from logarithm of edges to logarithm of vertices?

Well as you may recall, the number of edges is equal to at most,

in the worst case, the number of vertices squared.

Well the number of vertices squared is inside a log term.

So a log term will pull out the squared part and

that'll just go away as a constant factor.

And we' ll be left with the order number of edges times log of the number

of vertices still plus the number of vertices.

And that's it.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play