图中最短单程

Question

我是 Python 的新手，遇到了以下问题。正在考虑使用 BFS 解决，但没有。欢迎任何指点

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

感谢帮助

Answer 1

假设您从以下输入开始：

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

换句话说，我们将每个键映射到一个值（例如 'ORD' 映射到 'DNV'）。

行程的起点必须是未用作值的键（即不是其他航班终点的航班起点）。我们可以用

找到这个

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

它创建一组键和一组值，并找到不在值集中的键。

考虑到这一点，我们需要一种方法来构建停靠点列表。我们可以递归地这样做：

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

或作为循环

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

从那里，我们只需调用该函数：

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

或

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

图中最短单程

shortest single trip in the graph

python

shortest-path