尽管可能出现结局，但Breadth的算法却能永远运行下去。

Question

于是我看到了这道编码面试题，并试图解决它。我试图运用Breadth的路径查找算法来寻找从一个给定机场到其他所有机场的最优飞行路线；给定所有机场和路线的列表。航线中的元素意味着从第一个机场到第二个机场有一个单程航班。

我到了这里，这应该是找到从给定机场到所有其他机场的最短路线。但是当我运行时，它永远不会结束。

我想，我的算法没有把所有可能的下一个机场追加到我的路径上，但一切对我来说似乎都是o.k。

'''

import queue

airports = ["BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA",
            "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD"]

routes = [["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "SIN"],
          ["CDG", "BUD"], ["DEL", "DOH"], ["DEL", "CDG"], ["TLV", "DEL"], ["EWR", "HND"],
          ["HND", "ICN"], ["HND", "JFK"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"],
          ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"], ["LGA", "EYW"]]

main = "LGA"

def done(moves, aim):
    if moves == "":
        return False
    elif moves[-1][1] == aim:
        return True
    return False

def valid(moves, put):
    if moves == "":
        return False
    if moves[-1][1] == put[0]:
        return True
    return False

def available_starts(start, pos):
    anfaenge = list()
    for i in pos:
        if i[0] == start:
            anfaenge.append(i)
    return anfaenge


#MAIN ALGORITHM
kurzeste_moeglichkeiten = [] """all shortest possibilities"""
for port in airports:
    nums = queue.Queue()
    nums.put("")
    add = ""
    start = main
    if port != start:
        anfaenge = available_starts(start, routes) """possible startings"""
        for anfang in anfaenge:
            anfang = [anfang]
            nums.put(anfang)
        while not done(add, port):
            add = nums.get()
            for got in routes:
                if valid(add, got):
                    t = add
                    t.append(got)
                    nums.put(t)
        kurzeste_moeglichkeiten.append(add)

for eine in kurzeste_moeglichkeiten:
    print(eine)

'''

Answer 1

我已经设法用以下模块来表示你的图形 networkx 和 matplotlib. 正如你所看到的，机场被分成了两组。["SIN", "CDG"] 和 ["CDG", "SIN"] 是反向的，与你的其他数据是不可以的。

注：我用来显示图形的代码。

import networkx as nx
import matplotlib.pyplot as plt
airports = ["BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA",
            "LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD"]
legs = [["DSM", "ORD"], ["ORD", "BGI"], ["BGI", "LGA"], ["SIN", "CDG"], ["CDG", "SIN"],
          ["CDG", "BUD"], ["DEL", "DOH"], ["DEL", "CDG"], ["TLV", "DEL"], ["EWR", "HND"],
          ["HND", "ICN"], ["HND", "JFK"], ["ICN", "JFK"], ["JFK", "LGA"], ["EYW", "LHR"],
          ["LHR", "SFO"], ["SFO", "SAN"], ["SFO", "DSM"], ["SAN", "EYW"], ["LGA", "EYW"]]
main = "LGA"
G = nx.Graph()
for node in airports:
    G.add_node(node)
for leg in legs:
    G.add_edge(leg[0], leg[1])
plt.subplot(121)
nx.draw(G, with_labels=True)