2023年11月25日

Java代写 | DATA STRUCTURES AND ALGORITHMS PROGRAMMING ASSIGNMENT 3

本次美国代写主要为Java图算法的assignment

Shortest path

You’ve just accepted a new internship at Yahoo, in a city not yet supported by Google Maps. You
want to find the fastest route to the company from your house, but you don’t even have a map!
All you know is that your internship probably has a Yahoo sign on its building, and that it’s on an
intersection. The naïve way to find the shortest path would be to just take a direct route, but you
never know if the direct route has the most traffic. Another thing you could do is try every
possible path, but the run-time for that would be ridiculous (no pun intended). However, being a
data structures and algorithms student, you know that you can find the shortest path from your
house to the Yahoo building, even considering the traffic in the city, by using Dijikstra’s
Algorithm.
WHAT YOU’RE GOING TO BE GIVEN
We’ve coded a simulator of driving around this city for you. Starting at your home, you’ll be able
to go north, south, east, or west, and how many seconds it takes to get to the next intersection
with traffic. Each intersection will be a GraphNode object with the following methods:

• public int getX()
• public boolean hasNorth()
• public GraphNode getNorth()
• public int northWeight()
• public boolean hasSouth()
• public GraphNode getSouth()
• public int southWeight()
• public boolean hasEast()
• public GraphNode getEast()
• public int eastWeight()
• public boolean hasWest()
• public GraphNode getWest()
• public int westWeight()
• public boolean isGoalNode()
• public String getId()

Basically, each node can have a north node, south node, west node, and east node. For example, if
n is a node, if n.hasNorth() returns true, then it will have another node at n.getNorth(), and a
“cost” to get to that node.
Each node will have a unique string ID of 36 characters, in a format similar to this one:
5451397c-0d6e-4d7d-985f-bd627dcd2fcc

The characters will be different, but the dashes will always be in the same place. This is called a
Universally unique identifier (UUID). You will use this ID to store your nodes in a hash map,

allowing for easy indexing into the heap and so you can know which nodes need to be added to
the heap. You can get this id by calling node.getId().

There are also two public fields on the graph nodes (to make it easier). Their functions are
described later, but they are:

public int priority
public GraphNode previousNode
public String previousDirection

To get the GraphNode of your home, you need to have the following code:

GraphWrapper gw = new GraphWrapper()
GraphNode home = gw.getHome()

Do not touch the GraphWrapper.java or GraphNode.java files.