Кратчайший путь Networkx с условием по краям - python

Question

Давайте рассмотрим следующее Graph:

G = nx.Graph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F'])
G.add_edges_from([('A', 'B', {'walk': 3, 'time': 3}), ('A', 'C', {'metro': 4, 'time': 4}), ('A', 'D', {'walk': 3, 'time': 3}), 
                  ('C', 'E', {'walk': 3, 'time': 3}), ('D', 'E', {'walk': 3, 'time': 3}), ('B', 'F', {'walk': 3, 'time': 3}), 
                  ('D', 'F', {'metro': 4, 'time': 4}), ('E', 'F', {'walk': 3, 'time': 3})])
nx.draw(G, with_labels=True, font_color='white')

Для ребер можно увидеть три атрибута:

• walk - это время, необходимое для того, чтобы пройти одну остановку до другой (когда это возможно).
• metro - это время, необходимое для go от остановки до другого на метро.
• time равно walk или metro, и это вес, который я использую для nx.shortest_path (который позволяет мне получить путь, который занимает меньше времени, без необходимости выбирать между метро или ходьбой).

Теперь я хотел бы получить nx.shortest_path(G, 'A', 'F', weight='time') между узлами A и F с условием на пути: я хочу, чтобы shortest_path имел как можно меньше ребер walk.

В этом случае единственным shortest_path, который будет считаться хорошим, будет A -> D -> F, поскольку имеется только 1 walk ребро, в то время как у остальных по крайней мере два (даже если общее time для некоторых ребер короче).

Есть ли способ сделать это?

---

Редактировать: Я пытался использовать nx.all_shortest_paths(), чтобы получить несколько shortest_paths и затем выберите тот, который соответствует моим требованиям, но он не работает. nx.all_shortest_paths() действительно дает мне больше возможных коротких путей между source и target, однако во всех них уже слишком много walk edges. Решением было бы получить то, что считается shortest of shortest paths, и тот, который менее короткий, чтобы иметь больший выбор. Я, однако, понятия не имею, как мне поступить об этом.

Answer 1

Используя ваш пример:

Исходная сеть за вычетом "штрафа при ходьбе":

G = nx.Graph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F'])
G.add_edges_from([('A', 'B', {'walk': 3, 'time': 3}), ('A', 'C', {'metro': 4, 'time': 4}), ('A', 'D', {'walk': 3, 'time': 3}), 
                  ('C', 'E', {'walk': 3, 'time': 3}), ('D', 'E', {'walk': 3, 'time': 3}), ('B', 'F', {'walk': 3, 'time': 3}), 
                  ('D', 'F', {'metro': 4, 'time': 4}), ('E', 'F', {'walk': 3, 'time': 3})])
#nx.draw(G, with_labels=True, font_color='white')
nx.shortest_path(G, 'A', 'F', weight='time')

Вывод:

['A', 'B', 'F']

Теперь давайте оштрафуем время прохождения края путем умножения 10x:

G = nx.Graph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E', 'F'])
G.add_edges_from([('A', 'B', {'walk': 3, 'time': 30}), ('A', 'C', {'metro': 4, 'time': 4}), ('A', 'D', {'walk': 3, 'time': 30}), 
                  ('C', 'E', {'walk': 3, 'time': 30}), ('D', 'E', {'walk': 3, 'time': 30}), ('B', 'F', {'walk': 3, 'time': 30}), 
                  ('D', 'F', {'metro': 4, 'time': 4}), ('E', 'F', {'walk': 3, 'time': 30})])
#nx.draw(G, with_labels=True, font_color='white')
nx.shortest_path(G, 'A', 'F', weight='time')

Вывод:

['A', 'D', 'F']

Можете ли вы привести пример, где это не сработает, если вы достаточно оштрафуете свои "ходовые" края?