Homework 3
Graph and sorting algorithms
You are to write a program that finds the driving direction of a specified initial and end location much like MapQuest or Google Maps. You are to read the map information from a text file and create a graph. Each intersection and point of interest in the map will be given a unique name and be a vertex in the graph. Each road connecting 2 intersections is an edge in the graph. The edge names do not need to be unique. Use a directional graph since some streets may be one-ways.
The text file will look like:
Intersection Street Intersection Speed
Name Name Name Direction Distance Limit
Alafaya&GeminiN Gemini Gemini&GreekParkCt East .3 35
Gemini&GreekParkCt Gemini Alafaya&GeminiN West .3 35
Gemini&GreekParkCt Gemini Gemini&KnightCtE East .5 35
Gemini&KnightCtE Gemini Gemini&GreekParkCt West .5 35
Gemini&KnightCtE KnightCt Arena North .1 20
Arena KnightCt Gemini&KnightCtW South .1 20
Steps:
Write a function to perform a Quick Sort or Merge Sort on a list of alphanumeric data.
Read the text file and add each intersection name to the list. Only read the first column since all intersection names will be in there.
Sort the list using the Quick Sort or Merge Sort algorithm
Copy the names from the sorted list into the graph. Omit duplicates.
Create the graph by reading the original map file and adding an edge for each street. Use a binary search algorithm to find the proper vertex in the graph.
In the main program ask the user to input a start and end intersection.
Find the shortest and quickest path from the start to the end intersection. The output should indicate the name of the street and the distance.
The output should look like:
From Alafaya&GeminiN
Take Gemini East to Gemini&GreekParkCt .3
Take Gemini East to Gemini&KnightCtE .5
Take KnightCt North to Arena .1
The shortest path is the path with the least mileage while the fastest path is the path with the least time. The time is the distance multiplied by the speed in MPH.
You should have at least 20 intersections and 30 roads. You may share map files with other students. In fact, if you think you have a good map file allow me to have a copy for future students.
Hint the node structure for the graph should include the street name, direction like East, dist, and speed. The Graph array should include the intersection name and the pointer to the linked list.