QuestionQuestion

In this assignment, you will be asked to do two things related to graphs over a really cool data set. What I have done is to collect the city-to-city destinations for Spirit Airlines, the 7th largest airline in the United States. This airline services 58 airports in the United States, Canada, the Caribbean, Central America, and South America. There are 438 flights between distinct locations. Your job is to figure out the most efficient flight plan to get from a city of your choice that Spirit Airlines serves to some other city that it serves. We will do that in two different contexts: the fewest planes (a breadth first search) and the least time (Dijkstra’s algorithm).

You have been provided with a text file that includes the origin of a flight, the destination of a flight, and the amount of time that it takes (in minutes) to get from one location to another. You will need to construct a symbol table to do this.
Rather than to write algorithms to do this, search for implementations of BFS and Dijkstra for the language of your choice and then use that to complete this assignment. You will need to modify the algorithms slightly such that you can generate a text file of the results.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

from collections import deque

class node:
    def __init__(self, name):
       self.name = name
       self.adj = [] # neighbor node
       self.prev = None
       self.visited = False

class graph:

    def __init__(self, file):
       self.nodes = []
       self.setNode(file)

    def setNode(self, file):
       i = 0
       with open(file) as fin:
            for line in fin:
                if i == 0:
                   pass
                else:
                   ssplit = line.split()
                   name = ssplit[0]
                   source = None
                   for n in self.nodes:
                        if n.name == name:
                            source = n
                            break
                   if source == None:
                        source = node(name)
                        self.nodes.append(source)

                   name = ssplit[1]
                   dest = None
                   for n in self.nodes:
                        if n.name == name:
                            dest = n
                            break
                   if dest == None:
                        dest = node(name)
                        self.nodes.append(dest)

                   source.adj.append(dest)
                i = i + 1
            fin.close()...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$73.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats