Networkx находит кратчайший путь в порядке меток ребер ⇐ Python

[Anonymous]

Я работаю в аэропорту, и моя задача — рассчитывать маршруты руления самолетов на рулежных дорожках, обеспечивая соблюдение предписанной последовательности движения. Здесь я приведу пример и хотел бы спросить, существуют ли высокопроизводительные алгоритмы расчета кратчайшего пути с соблюдением заданной последовательности маршрутов с использованием Python.

Код: Выделить всё

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_edge("A1", "A2", weight=1, name="A")
G.add_edge("A2", "A3", weight=1, name="A")
G.add_edge("A3", "A4", weight=1, name="A")
G.add_edge("A4", "A5", weight=1, name="A")
G.add_edge("A5", "A6", weight=1, name="A")

G.add_edge("A2", "B1", weight=1, name="B")
G.add_edge("B1", "B2", weight=1, name="B")
G.add_edge("B2", "B3", weight=1, name="B")

G.add_edge("A6", "C1", weight=1, name="C")
G.add_edge("C1", "C2", weight=1, name="C")

G.add_edge("B2", "D1", weight=1, name="D")
G.add_edge("D1", "D2", weight=1, name="D")
G.add_edge("D2", "D3", weight=1, name="D")
G.add_edge("D3", "C2", weight=1, name="D")

G.add_edge("D1", "E1", weight=1, name="E")
G.add_edge("D2", "E1", weight=1, name="E")
G.add_edge("E1", "E2", weight=1, name="E")

# draw
pos = nx.spring_layout(G, seed=22)
nx.draw_networkx_nodes(G, pos, node_size=300)
nx.draw_networkx_edges(G, pos, width=1)
nx.draw_networkx_labels(G, pos, font_size=10, font_family="sans-serif")
edge_labels = nx.get_edge_attributes(G, "name")
nx.draw_networkx_edge_labels(G, pos, edge_labels)
ax = plt.gca()
ax.margins(0.0001)
plt.axis("off")
plt.tight_layout()
plt.show()

Например :
Если источник = "B3" и цель = "E2", а порядок последовательности маршрутов = ["B", "A", "C" ", "D", "E"], то вычисленный результат должен быть: ["B3", "B2", "B1", "A2", "A3", "A4", "A5", "A6", "C1", "C2", "D3", "D2", " E1", "E2"].
Если источник = "A1" и цель = "B3", а порядок последовательности маршрутов = ["А", "Б", "Д", "Е", "Д", "B"], то вычисленный результат должен быть следующим: ["A1", "A2", "B1", "B2", "D1", "D2", "E1", "D1", " B2", "B3"].

Подробнее здесь: https://stackoverflow.com/questions/792 ... abel-order