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...

I need help with this assignment all instructions are in the HW 3 word document file.


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 StreetIntersectionSpeed NameNameNameDirection DistanceLimit Alafaya&GeminiNGeminiGemini&GreekParkCtEast.335 Gemini&GreekParkCtGeminiAlafaya&GeminiNWest.335 Gemini&GreekParkCt GeminiGemini&KnightCtEEast.535 Gemini&KnightCtEGeminiGemini&GreekParkCtWest.535 Gemini&KnightCtEKnightCtArenaNorth.120 ArenaKnightCtGemini&KnightCtWSouth.120 Steps: 1. Write a function to perform a Quick Sort or Merge Sort on a list of alphanumeric data. 2. 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. 3. Sort the list using the Quick Sort or Merge Sort algorithm 4. Copy the names from the sorted list into the graph. Omit duplicates. 5. 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. 6. In the main program ask the user to input a start and end intersection. 7. 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. Alafaya&Gemini Gemini Gemini&GreekPark East 0.2 35 Alafaya&Gemini Alafaya Alafaya&Centaurus South 0.35 45 Alafaya&Centaurus Alafaya Alafaya&Gemini North 0.35 45 Alafaya&Centaurus Centaurus Centaurus&Gemini East 0.1 35 Alafaya&Centaurus Alafaya Alafaya&University South 0.3 45 Centaurus&Gemini Gemini Aquarius&Gemini North 0.05 35 Centaurus&Gemini Centaurus Alafaya&Centaurus West 0.1 35 Centaurus&Gemini Gemini WestGarage South 0.05 35 Aquarius&Gemini GreekPark Gemini&GreekPark North 0.3 30 Aquarius&Gemini Aquarius Aquarius&PegCirc East 0.4 30 Aquarius&Gemini Gemini Centaurus&Gemini South 0.05 35 Gemini&GreekPark Gemini Alafaya&Gemini Northwest 0.2 35 Gemini&GreekPark GreekPark Aquarius&Gemini Southwest 0.3 30 Gemini&GreekPark Gemini Gemini&KnightCt East 0.4 35 WestGarage Gemini Centaurus&Gemini Northeast 0.05 35 WestGarage Gemini Gemini&Lynx Southwest 0.05 35 Gemini&Lynx Lynx LynxStation East 0.1 25 Gemini&LynxGeminiWestGarageNorth0.0535 Gemini&LynxGeminiGemini&UniversitySouth0.135 LynxStation Lynx Gemini&Lynx West 0.1 25 Gemini&University Gemini Gemini&Lynx Northwest 0.15 35 Gemini&University University Alafaya&University Southwest 0.15 45 Gemini&University Gemini Millican East 0.2 35 Alafaya&University Alafaya Alafaya&Centaurus North 0.3 45 Alafaya&University University Gemini&University Northeast 0.15 45 Millican Gemini Gemini&University West 0.2 35 Millican Gemini SouthGarage Southeast 0.1 35 SouthGarage Gemini Millican Northwest 0.1 35 SouthGarage Gemini RecCenter South 0.25 35 EastGarage Gemini Gemini&Orion North 0.2 35 EastGarage Gemini Gemini&Libra South 0.45 35 RecCenter Gemini SouthGarage West 0.25 35 RecCenter Gemini Gemini&Libra East 0.25 35 Gemini&Libra Gemini RecCenter Southwest 0.25 35 Gemini&Libra Gemini EastGarage Northeast 0.45 35 Gemini&Libra Libra