[MUSIC]

This video is the project overview for week three.

Extending and improving graph search.

Specifically, where gonna be doing shortest path on a weighing graph.

There's two key parts to this assignment.

The first is Dijkstra's algorithm, and the second is aStarSearch.

Now again, both of these methods are gonna find us the shortest path in

the weighing graph.

A store search will just do so a little more quickly than Dijkstra search does.

You're gonna be working with the same code as you did in week two.

And we're working with MapGraph.java in the roadmap package.

And you may find that you have to revise more than just MapGraph.java.

You may have to modify some of your other classes within your class organization in

order to support these methods.

And we'll talk about those details in just a little bit.

If you weren't entirely happy with your week two solution.

You can feel free to use our week two solution as a starting point for

week three.

But I do encourage you to use your own code.

As it's likely that you'll be more comfortable with your own code.

So again, you're gonna be authoring two main search methods

that we've learned about this week.

The first, again, is dijkstra.

The second is aStarSearch.

Both these methods take a start point and a goal point.

And your goal is to find the shortest path from the start to the goal.

You're also gonna take this third parameter that we recognize from

the breadth research, which is this consumer object.

Now again, the consumer object exists that you can report the nodes as you're

visiting them.

In order to visualize them with our application.

And we'll talk about the details of how to do that in just a little bit.

For testing purposes you may want to just use the dijkstra,

the aStarSearch that don't require this consumer object.

You can just call these methods.

And we'll create that main consumer object,

and then we'll call your Appropriate method.

You don't need to modify these methods.

These are just useful for the testing.

Your first step is gonna be authoring Dijkstra's algorithm.

Now this shouldn't be too bad.

You'll be able to use your breadth first method from week two as a starting point.

And you can use the pseudocode from the videos from this week.

The biggest changes that you'll need to make for

this week are actually modifying your MapGraph

class along with your support classes to be able to facilitate this search.

Specifically, right at the start of Dijkstra's algorithm we say initialize

the distance to each of the vertices or nodes to positive infinity.

And that essentially allows us to keep track of a current distance from my start

node to each of the nodes.

It's likely that within your class structure,

you didn't keep some kind of distance like this associated with each of the nodes.

Now whether or not what you wanna add a current distance to the nodes, or

you wanna make a wrapper class to store that there, or you want some entire other

data structure to keep those current distances is all up to you.

You'll just need to keep track again of this distance

from the start node to the vertex as your algorithm progresses.

So, the second piece is this is likely your first time working with

a priority queue.

And when you insert items into a priority queue.

You need to have some ordering of their priorities.

In this case, you're gonna be using the distance from their start node to

prioritize them.

And with a shorter distance being a higher priority than a longer distance.

In order to do this, whatever element you're inserting into the PriorityQueue.

And this element's likely gonna store both the node itself as well as the distance to

that node.

Needs to implement the interface comparable.

And to implement the interface comparable you need to author the compareTo method.

You can look at the javadocs for Comparable for more details.

If you want to use the visualization tool in the provided GUI just as we did

our project overview video.

You're gonna need to report removal of nodes from the queue to

this consumer object.

And you're gonna do so by using the accept method.

And that takes a geographic point.

So for example you may have, you may call the except method on your node search.

Then pass it, geographic point.

Where you're assuming here that next is the element that you just removed from

the priority queue.

And that the getLocation gets you that geographic point associated with the node

that you just removed.

Next step, just like with all other methods in this course.

You're gonna wanna test your code.

So after you've coded Dijkstra.

I encourage you to try a number of simple test cases.

Let's look at the example that we just looked at from week two for breadth for

search, and figure out what should Dijkstra return back as the shortest path.

In this example, the first search found us the shortest path by visiting

the fewest number of vertices.

Breadth for search found us the path from 1,1 to 8,-1 by

going through 4,1, then 7,3, and then to The 8, -1.

But this actually isn't the shortest path.

So we hope Djikstra will actually do is find the shortest path and

the shortest path here should be from 1,1 to 4,1 to 5,1 to 6.5, 0 to 8,-1.

Now that we have a good idea of what it should do.

Let's look at how we would do this with our code.

In order to test Dijkstra on this example.

We've provided you simpletest.map as a data file,

which contains this exact example.

What you could do is run Dijkstra on this.

And it should find the same shortest path as we just worked through.

I encourage you to try some additional test cases to check to make sure

that your algorithm is actually working properly.

Your next step in the project is going to be authoring AStarSearch.

So your gonna always look back at the videos from this week for

the pseudo-code for AStarSearch.

And you'll likely will use your Dijkstra method from this week as a starting point.

Now there are some critical changes to be made going from Dijkstra to AStarSearch.

But again, much of the work that you're gonna need to do for

this part of the project is in changing around your classes

to you'll support now the storage of two distance values, not just one.

You'll still need to maintain the actual distance from the start.

Just as you did with Djikstra.

But you'll also need to keep a predicted distance,

which is the actual distance to the node.

Added to the straight line distance from this node to the goal.

And you're gonna use the predicted distance in the priority queue to

prioritize better paths.

As a hint, be sure when you start your algorithm to initialize both your

actual and your predicted values to positive infinity.

And it set both of those values to be zero for the start node.

Just like we did with Dijkstra.

If you wanna use the visualization tool,

you'll again want to use this accept method on the consumer object.

But we want to test AStarSearch in two ways.

The first is that we wanna make sure that AStarSearch returns the same

answer as Dijkstra.

So it should be finding the same shortest path.

The biggest distance between AStarSearch and Dijkstra is the number of nodes

that get visited on the path to finding your solution.

So you could look at the previous example.

What you see in our previous example is a Dijkstra diagram's actually gonna visit

all the nodes in this graph in the process of trying to find it's path from 1,1 to

8,-1.

AStarSearch is gonna do this much more efficiently.

It's gonna find the path from 1,1 to 8,

-1 by only exploring nodes in fact on the shortest path.

In order to test this, you can use the simpletest.map file in the data folder.

Run Djikstra on it and look at the nodes it visited.

It should visit essentially these nine nodes in this order.

You can run then AStarSearch on it,

and it should visit these five nodes in this order.

You might be asking, well how do I know which nodes are being visited?

And the best way to do that is to just print out nodes as they get visited

to help with the bugging.

And then you'll want to comment out whatever that print is

before you start running it on larger examples.

I encourage you to run your code, not only in this example, but in others to see if

AStarSearch is in fact finding a shorter path by visiting fewer nodes.

In fact, one of the best parts of this assignment is running this in the GUI.

And you'll see Dijkstra exploring tons of nodes in the path and

finding the shortest path from one location to another.

Whereas AStarSearch does such a more efficient job,

looking at only the nodes on a reasonable path from the start to the goal.

Once you're happy with your code for both Dijkstra and AStarSearch.

You're gonna submit your code just as you did with week two with

zipping all the files in the roadgraph package into one zipfile called mod3.zip.

And then you're gonna go, just like we did with previous assignments.

You're gonna go to My submission, you're gonna create a new submission.

And you're gonna submit your zip file and

you'll get feedback about how well it performs.

You can always look at the feedback from the graders to see what went wrong.

And you can always look at the graders themselves in our source code

to see what tasks are being performed.

>> There is one last piece to this assignment, and the quiz it's coming up.

We will ask you to provide the number of nodes that are visited, using Djikstras

algorithim, as well as using aStarSearch out of them on one of our test cases.

This is one of my favorite assignments in this course.

I hope you have a lot of fun with it.

Good luck.

Project: Shortest Path Programming Assignment Walkthrough

Advanced Data Structures in Java

Conoce a los instructores