Finding Shortest Flight Paths Solution

Description

This assignment should be completed individually. Advice: start as soon as the homework assignment is assigned, so you have plenty of time to get the code to compile, have time to test, have time to debug, have time to re-test, and have time to complete the summary report.

Specification

You will complete the code to implement Dijkstra’s algorithm (shortest paths from single source node) to find the shortest flight plan (in total mileage) between a source city and destination city.

For example, if the user types:

./routeFinder SampleRoutes.txt PDX IAD the program reports:

The path is 3 flight(s) long:

PDX -> SEA -> ORD -> IAD.

2433 miles.

The small graph sample in SampleRoutes.txt consists of a set of 18 (line 1) airports with the airport names listed alphabetically first (lines 2- 19) followed by the flights between the cities (lines 20-end). Graph is directed, so if the flight connection is from A-B but not from B- A, the connection B-A is not listed in the flight connection list. If there is a flight from PDX to SEA, and a flight from SEA to PDX then both flight connections are listed but don’t assume they have the same distance. The graph is weighted by the mileage between the two airports. The mileages and connections are from www.world-airport-codes.com/distance/ or https://www.transtats.bts.gov.

Open graph.h. The graph is implemented as an adjacency list.

A node in the adjacency list contains:

the destination

cost

next node in the list.

An adjacency list object represents a single vertex in the graph and contains:

airport name (3-letter code)

predecessor (for dijkstra’s algorithm)

color (for dijkstra’s algorithm)

dValue (for dijkstra’s algorithm)

head (pointer to head of linked list of adjacent nodes)

The entire graph is represented as:

V (number of vertices in the graph)

array (the array of adjacency list objects)

jump (mapping from node numbers, 0 through |V|-1, to airport codes)

It might be helpful at this point for you to draw a simple graph of a few nodes and convert the graph to the code representation. Before asking for homework help, be sure that you do this step to ensure you understand the graph data structures.

Open graph.c to see how the functions are implemented. Note that this assignment does not ask that you alter the graph representation, but reviewing these functions will help you understand how the adjacency list representation is implemented.

Now open main.h. This file defines a few constants (for command line arguments) and the prototypes for the functions defined in main.c and the new file dijkstra.c that you will create. You will implement the following three functions: dijkstra, isEmpty, and getMin.

Open main.c. This file creates the set of vertices (airports) and checks that the program is being run correctly. It checks that the airport names given at the command line are in the graph. If not, it reports an error and exits. Then, the airports are sorted and a graph with these airports is constructed. In the buildGraph function, you will see the flights (edges) that exist between airports. Then, dijkstra is called from the source. The path is found, starting at the destination and working through the predecessors back to the source. The total number of flights along the shortest path, the path, and the total mileage is printed to the screen. Finally, the graph object is freed.

At this point, you should have a good idea what the starter code does. If you have questions, please ask.

GET STARTED

0. Implement the freeGraph function at the bottom of the graph.c file. The function should free all structures allocated on the heap. This should force you to understand how the graph and application logic is implemented. Run your code through valgrind to make sure you implemented the free function correctly

valgrind ./routeFinder AllUSRoutes.txt PDX SFO

Next:

* Remove the block comment by deleting the lines 56 and 131 in main.c * Alter the makefile as needed

1. Create a new file called dijkstra.c in the same directory as the other files. At the top, include <stdio.h>, <stdlib.h>, <string.h>, “main.h”, and “graph.h”.

Implement the following functions (can copy and paste function prototypes from main.h):

	isEmpty				should return 1 if there are no white nodes in the
	o	Note: This function
		graph g (all have been colored black by dijkstra). It should return 1 if
		the graph is null. It			should return 0 if there is at least one white node in
		the graph g.
	o Hint: g->array[i].color is the color of the ith vertex in g.
	getMin
	o	Note: This function should return the index of the smallest white node
		in the graph g.
	o If the graph is null, return -1.
	o	Hint: iterate through the graph; if the node is white, check to see if its
		dValue is smaller than the smallest found so far; if so, update the
		smallest value and index to this node.
	o If the graph has no white nodes, return -1.
	dijkstra
	o	Note: This function should implement dijkstra’s algorithm from the src
		node to find all the shortest paths from src to other nodes in the graph
		g. When the function is finished, all dValues for all nodes should be set,
		all nodes’ colors should be black, and all nodes’ predecessors should
		be set.
	o Note: At the beginning (graph is initialized), the nodes’ colors are set to
		white. If this function was to be called more than once in a program,
		we would need to set all nodes’ colors to white. So, you may assume g-
		>array[i].color is white for all values of i when g is passed in to dijkstra.
	o You should implement the algorithm as follows:
			Find node number for src (go through the labels of the vertices
			and return the index of the node when the src string is equal to
			the label; you can use strcmp or strncmp to compare strings).
		Set the source node’s dValue to 0.
			While the graph is not empty (use isEmpty function):
				Let U = getMin(g) //use getMin function
				For each neighbor N of U:
				o	If N’s dValue > [U’s dValue + cost(U, N)], update
					N’s dValue to [U’s dvalue + cost(U, N)]. Also,
					update the predecessor for N to be U.
			Set U’s color to black

At this point, you should be able to compile and run the program:

make clean; make

routeFinder SampleRoutes.txt PDX IAD

(or)

./routeFinder SampleRoutes.txt PDX IAD

The implementation prints out a bunch of information about the graph and then the shortest path information as at the end.

Documentation

The code should be well-commented, well indented, use consistent bracing, and include enough whitespace to be readable. The dijkstra.c file should have a block comment at the top that includes information about the author and included code. Each function should have a header comment. See the file posted to moodle about good style that was generated by the CS 305 students.

Test cases

You should try running the program of several pairs of cities (some that are not in the graph and some that are).

Test your code on both test files provided. The AllUSRoutes.txt uses what US Government’s FAA has in its database as far as the airports go and I pulled all flights for all carriers for 2017 to establish the connectivity between individual airports. Your code has to work on files SampleRoutes.txt and AllUSRoutes.txt.

Graph is not connected, so some airports serve only local connections (or the FAA’s list keep the airports without service, or the airports are military without commercial carrier service), but not to other US cities.

Try to find the longest air route

Try to find the route with most connecting flights (will still be shortest route)

Additional Enrichment

If you have time, you may try writing the graph data structures from scratch instead of using the starter code.

You could try modifying the graph so it is undirected instead of directed. But, be sure to save your original code in a directory and put the new code in a separate directory.

You could try adding flight times and check that the flights depart after the earlier flights land in the path. (This will require some substantial changes to the existing code.) Be sure to save your original code in a directory and put the new code in a separate directory.

Please document the additional features in your code and your written summary.

This is not extra credit per se, but a chance for you to do some exploration.

Logistics

1. Download the starter code located on Moodle. If using Linux, you can unzip it with the unzip <name of zip file> command. You may use any IDE that you can find for C or just a text editor (emacs) to write your code. However, your code must compile with gcc on the EGR Linux machines. It is to your advantage to make sure your code compiles with gcc on the Linux computers, since that is used for grading.

2. When you are finished and ready to submit:

1. 1. Create a new folder called username_HW5.

   2. Put all starter code, your dijkstra.c file, and makefile in this folder.

1. 3. Copy your HW5Summary.docx file into this folder.

   4. Zip the folder by right-clicking and Send To->Compressed Folder (on Windows). There should also be a zip utility on Mac.

2. What to turn in: Submit your username_HW5.zip file to Moodle before the due date and time. After logging into learning.up.edu, navigate to CS 305. You will find a link to submit this file. You do not need to print anything for this homework submission.

Grading Guidelines (total of 20 points)

Your files will be graded in three separate categories:

(5 points) Code Quality: Design, commenting, whitespace, readability, proper indentation, consistent naming conventions, good variable names

(10 points) Code Operation: Does code do what is listed in the specification? Note: code that does NOT compile will receive 0 points for code operation.

o 2 points freeGraph o 1 points isEmpty o 1 points getMin

o 6 points dijkstra

(5 points) Summary report: Completeness, correctness, and clarity

HW 5 Report Guidelines and Format – use the template provided below.

Include the questions in your write-up.

Name: CS 305 HW 5 Report

1. Questions (include these in your write-up):

1a. (.5 pt) If your program does not meet the specifications, please note the differences and anything that is not working correctly. If it works, write “Meets all specifications.”

1b. (1.5 pts, 0.25 pts each) What is the output from your program for the following
pairs of cities? (The top row has been done for you.)
Source	Destination	Path	Miles
PDX	MCO	PDX -> ATL -> MCO	2572
LAX	PVD
ATL	JFK
SEA	LAX
PHX	DEN
PVD	JFK
DFW	ATL
MTM	MRI
HIB	HIO
INL	ZZV
WWD	YUM
YAK	BAF
AVL	BIF

2. (1 pt) Use Prim’s algorithm to find the minimum spanning tree for the following subset of the airport graph. Start the algorithm using vertex LAX.

1658 DFW

SEA 1168

1051 ^SAN

130

2440 ₁₀₉

PDX		835		LAX
2447				1942
	JFK		2168	ATL

3. (1.5 pts) Show each step of Kruskal’s algorithm for finding the minimum spanning tree for the graph in #2. Draw the minimum spanning tree at each step of the algorithm. For example, the first step would be to put edge (PDX, SEA) into the spanning tree. Be sure to enumerate all the steps and show the final minimum spanning tree. (For the graph above)

• a. (.25 pt) How much time did you spend in total on this homework assignment (including the report)?

• 2. (.25 pt) What was the most challenging part for you when completing this assignment?

Appendix A: (copy this statement if it applies to you) I verify that the code and this write -up were authored by me. I have documented the help I have received in comments in the code files. I have not distributed my code to anyone else except via this homework submission.

Appendix B: Copy and paste your dijkstra.c here (use Courier New 8pt font so the characters line up correctly)