Dijkstra’s Shortest Path

0. Complete the Prerequisites

Before continuing on, make sure you’ve pulled the starter code.

After being stuck at home due to a rigorous summer course load, you have decided to take a cross country road trip, starting from Chapel-Hill and ending Los Angeles. Along the way you would like to make some stops and to visit some new places! It is up to you, using Dijkstra’s Algorithm, to figure out the most optimal way from CH to LA.

However, optimal does not necessarily mean the shortest. We have provided you a list of the paths between every city and its corresponding distance, scenery, and traffic. We also gave some attractions in each city that may (or may not) interest you. This assignment has 2 parts: Creating your weights, and implementing Dijkstra’s algorithm

1. Creating Weights

The excel sheet titled roadtrip is what you need to fill in with numbers that you want to assign each factor.

Link: https://docs.google.com/spreadsheets/d/1mB565mYrsWRLblfatBxrCXQe-3W9pQlL9fs46IYI_pE/edit?usp=sharing

This link is view only, in order to edit it, go to file -> make a copy and that will create an editable copy of the file in your Google Drive. The distance column is pre-filled in for you, but based on the details at the bottom of the instructions you should assign scores for each of the other categories (for example, you can assign heavy traffic a 5 and medium traffic a 3). These numbers are completely up to you; if scenery is not something you value in a roadtrip, the entire scenery column can be 0s. Since roads go both ways, this graph is an undirected graph. Each row in the excel sheet represents a road going one way. The starter code given takes care of making the edges go both directions, so all you need to do is fill in the numbers for each category. Once you filled in all of those, save and download your excel sheet as a .csv file (File -> Download -> Comma seperate values) and take a look at Graph.java. The createGraph method reads each line from your csv file and passes in the source and destination cities, and the distance, traffic, scenery, and attractions scores that you assigned to readLine(). ReadLine() then calls calculateWeight() and passes in those same arguments.

IMPORTANT In order to create a graph (in Main.java), you must pass in to the contstructor the path for where your csv file is stored. If you pass in the incorrect path you will get a FileNotFoundException.

How to find your file path:

Mac: Locate the file in your finder and right click on it. Hold down the option key and select ‘Copy “roadtrip.csv” as Pathname’. The absolute path of your file is now copied to your clipboard.

Windows: Locate the file in your file explorer, shift + right click on file, then select “Copy as path”

The calculateWeight method is where you create your algorithm using 4 factors to produce a single weight for your edge. However, make sure you are not doing any illegal math operations. For example if you divide a number by traffic, make sure you never pass in 0 for traffic since you cannot divide by 0. You can also choose to emphasize certain factors over others. For instance if your car gets really bad gas mileage, you could give distance more weight as opposed to scenery. Also be sure that your weights are positive. Dijkstra’s algorithm does NOT work with negative values.

Once you have completed this part, Write 1 paragraph explaining your reasoning behind your scores for each category, and how your algorithm works. Write this paragraph in the Explanation.txt file provided.

2. Implementing Dijkstra’s Algorithm

Part 2 of this project is to implement Dijkstra’s algorithm, using a priorty queue. The package minBinHeap contains the code for a Minimum Binary Heap that you will be using for your algorithm (do not edit anything in that folder). The Dijkstra method in Graph.java should return a Map with the key being the name of the city, and the value being the total weight that it takes to reach that city from your starting point. Once you are confident your algorithm works, add to your Explanation.txt file an overview of your roadtrip. Give us 1 paragraph explaining what cities you are going to hit between Chapel Hill and LA, the weight of each path you take and what attractions you’re planning to visit on the way (this doesn’t necessarily have to be the ones list below).

Attractions

Chicago

• The Bean
• Wrigley Field
• Deep Dish Pizza

Nashville

• Country Music Capital
• Grand Ole Opry
• Centennial Park

Dallas

• Six Flags
• Dallas Arboretum and Botanical Garden
• Sixth Floor Museum at Dealey Plaza (museum about the JFK assassination)

Las Vegas

• Las Vegas Strip
• Red Rock Canyon
• Bellagio Hotel and Casino

Phoenix

• Desert Botanical Garden
• Camelback Mountain
• Papago Park

Denver * Red Rocks Park and Amphitheatre * Great Skiing Resorts * Denver Art Museum

San Francisco

• Golden Gate Bridge
• Alcatraz Island
• Fisherman’s Wharf

Los Angeles

• Potential Celebrity Citings
• DisneyLand
• Santa Monica Pier

Road Information

CH - Nashville:

• Scenery: Nice, you drive through the Pisgah National Forest
• Traffic: No traffic

CH - Chicago

• Scenery: Mostly highway but a nice drive through the West Virginia mountains
• Traffic: Low

CH - Dallas

• Scenery: Pretty drive through hills and forests
• Traffic: Heavy

Vegas - San Francisco

• Scenery: Goes through Death Valley National Park
• Traffic: Average traffic

Dallas - Phoenix

• Scenery: Mostly farms and fields
• Traffic: Heavy traffic

Dallas - Denver

• Scenery: Desert scenery, mainly flat
• Traffic: Moderate traffic

Denver - Chicago

• Scenery: Midwestern Scenery
• Traffic: Low

Denver - Nashville

• Scenery: Most of drive is through forests and open fields
• Traffic: No traffic

Chicago - Vegas

• Scenery: Pass through 4 states with changing scenery, from fields to desert
• Traffic: Medium traffic

Chicago - San Francisco

• Scenery: Some national forests on the way
• Traffic: None

Vegas - Phoenix

• Scenery: Desert scenery
• Traffic: High

Phoenix - LA

• Scenery: Desert scenery
• Traffic: Low traffic

Phoenix - Denver

• Scenery: Many national forests
• Traffic: Moderate

LA - San Francisco

• Scenery: Incredible ocean views on Pacific Coast Highway
• Traffic: Light

3. Make a Backup Checkpoint “Commit”

“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.

1. Select the Git menu along the top of your screen and then choose “Commit”.
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Ensure all the files that you’d like to backup are selected. Your cursor should be inside of a message box where you will write a nice description of the modifications you’ve made to your code, like “Finished EX04!”, and then hit the “Commit” button.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
   • IntelliJ might tell you there are some warnings or errors here, and you should just commit anyway!
4. If you open the Git at the bottom of your screen, you should see this commit added to your chain of git commits. However, it has just been added to your local main branch, and needs to be pushed to your remote backup.
5. Select the Git menu along the top of your screen again and then choose “Push”.
6. A pop-up should appear that displays: “main -> backup : main”, which means your latest local commit on the local main branch is going to be pushed to the main branch on the remote backup. If you see “main -> origin : main”, just click where it says origin and select backup. Hit the “Push” button.
7. If you want to see your backed up work on Github, navigate to the following URL but replace USERNAME with your GitHub username:
   • https://github.com/summer-210/summer210-workspace-USERNAME
   • You can also verify it was pushed successfully by opening the Git view along the bottom of your screen and verifying the latest commit appears on the local and remote branches. (The text next to the tag icons should say backup & main, next to the latest commit message)

4. Submit to Gradescope for Grading

All that’s left now is to hand-in your work on Gradescope for grading.

Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!

Login to Gradescope and select the assignment named “EX14 - Dijkstra” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.

Mac Users

IMPORTANT This is different! The submission script isn’t updated to work for this one.

Navigate to your ex14 folder in a Finder window. Right click on it, and hit “compress ex14”. This will create a zip of ex14 in the same directory. You can rename it if you want. Submit this to gradescope.

Windows Users

Until then, please navigate to your course workspace in a File Explorer window. Then right click on the src folder in your exercises directory and compress the directory into a zip folder. You can name it “ex14_submission.zip”

When you upload it to Gradescope, please delete any files that showed up in the src/ folder that were not actually part of ex14.