CODEWITHSUNDEEP
pythonshortest-path
Pankaj
Pankaj

Reputation: 65

shortest single trip in the graph

I am new to Python and stuck on below problem. Was thinking of Solving with BFS, but no. Any pointers welcome

Given a list of flights (in any order), construct the trip that this list represents. For example, if we have a flight from San Francisco to Los Angeles and a flight from New York City to San Francisco, the trip is "NYC to SFO to LAX". Assumptions:

  • A city will only be visited once per trip. (you can't go back to a given city after visiting it).
  • The list will only represent one single trip.
  • Input is not from a text file. We can consider any data structure for the input, no specifications.
# Flights:
# ORD -> DNV
# SFO -> NYC
# LAX -> SFO
# NYC -> ORD
# 
# Trip / Output:
# LAX -> SFO -> NYC -> ORD -> DNV

Appreciate the help

Upvotes: 0

Views: 273

Answers (1)

RagingRoosevelt
RagingRoosevelt

Reputation: 2164

Lets assume that you start with the following input:

flights = {'ORD': 'DNV', 'SFO': 'NYC', 'LAX': 'SFO', 'NYC': 'ORD'}

In other words, we map each of the keys to a value (eg 'ORD' maps to 'DNV').

The origin of the trip must be the key that isn't also used as a value (ie the start of a flight that isn't the end of some other flight). We can find this with

origin = set(flights.keys()).difference(set(flights.values())).pop()

which creates a set of keys and a set of values and find the key that isn't in the set of values.

With this in mind, we need a way to build the list of stops. We can do this recursively:

def get_flights(route, flights):
    if len(route) == 0:
        origin = set(flights.keys()).difference(set(flights.values())).pop()
        return get_flights([origin], flights)
    elif route[-1] in flights:
        return get_flights(route + [flights[route[-1]]], flights)
    else:
        return route

or as a loop

def get_flights_2(flights):
    origin = set(flights.keys()).difference(set(flights.values())).pop()
    route = [origin]

    while route[-1] in flights:
        route += [flights[route[-1]]]

    return route

From there, we just call that function:

" -> ".join(get_flights(flights))

or 

" -> ".join(get_flights_2(flights))

Upvotes: 1

Related Questions