Генерация маршрута / пути с ограничениями в графе (python)

Question

Я рассматриваю (publi c транспортную) линию с 7 узлами / станциями [A, ..., G] и различными услугами [быстро, медленно]. С определенными узлами, где возможны передачи [A, D, G]. В качестве сетевого представления я решил добавить фиктивный узел в узлы, где возможна передача (красная ссылка на изображении). Красные ссылки имеют атрибут передачи со значением 1, остальные ссылки имеют атрибут передачи со значением 0. Для пояснения добавлено изображение.

Представление линий и графиков

Я создал функцию в python, которая возвращает все возможные маршруты из определенного источника i в пункт назначения j в графе G , с соответствующим общим весом путей. Он печатает список всех посещенных узлов и общий вес в качестве последнего элемента.

Для маршрутов от узла 0 к узлу 6 вывод:

[[0, 1, 2, 3, 4, 5, 6, 35000], [0, 1, 2 , 3, 8, 9, 6, 36680], [0, 7, 8, 9, 6, 36680], [0, 7, 8, 3, 4, 5, 6, 36680]]

Сейчас я пытаюсь добавить два ограничения в генерацию маршрута:

1. Исключить маршруты, используя более 1 линии передачи
2. Исключить маршрут в 2 раза длиннее, чем самый короткий маршрут

Где, маршруты от узлов передачи хранятся в том же наборе маршрутов. Например, маршрут от A до G должен включать в себя маршруты от 0 до 6 и маршруты от 7 до 9.

В конце концов, ему необходимо получить веса маршрутов, чтобы рассчитать вероятность выбора определенного Маршрут от i до j и отслеживание маршрутов, по которым передается ссылка.

У кого-нибудь есть идеи о том, как это реализовать?

Код приведен ниже.

import networkx as nx
import dict_digger


# transfer data
Res_T = 14*60

# distances in meters
d1 = 4000
d2 = 4000
d3 = 8000
d4 = 6000
d5 = 6000
d6 = 7000

# make graph
G = nx.MultiDiGraph()

# links A - B
G.add_edge(0, 1, weight = d1, transfer = 0)
G.add_edge(1, 0, weight = d1, transfer = 0)

# links B - C
G.add_edge(1, 2, weight = d2, transfer = 0)
G.add_edge(2, 1, weight = d2, transfer = 0)

# links C - D
G.add_edge(2, 3, weight = d3, transfer = 0)
G.add_edge(3, 2, weight = d3, transfer = 0)

# links D - E
G.add_edge(3, 4, weight = d4, transfer = 0)
G.add_edge(4, 3, weight = d4, transfer = 0)

# links E - F
G.add_edge(4, 5, weight = d5, transfer = 0)
G.add_edge(5, 4, weight = d5, transfer = 0)

# links F - G
G.add_edge(5, 6, weight = d6, transfer = 0)
G.add_edge(6, 5, weight = d6, transfer = 0)


# links A' - D'
G.add_edge(7, 8, weight = d1+d2+d3, transfer = 0)
G.add_edge(8, 7, weight = d1+d2+d3, transfer = 0)

# links D' - G'
G.add_edge(8, 9, weight = d4+d5+d6, transfer = 0)
G.add_edge(9, 8, weight = d4+d5+d6, transfer = 0)

# transfer link A - A'
G.add_edge(7, 0, weight = Res_T, transfer = 1)
G.add_edge(0, 7, weight = Res_T, transfer = 1)

# transfer link D - D'
G.add_edge(8, 3, weight = Res_T, transfer = 1)
G.add_edge(3, 8, weight = Res_T, transfer = 1)

# transfer link G - G'
G.add_edge(9, 6, weight = Res_T, transfer = 1)
G.add_edge(6, 9, weight = Res_T, transfer = 1)


def find_path(G, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if start not in G:
        return None
    for node in G[start]:
        if node not in path:
            newpath = find_path(G, node, end, path)
            if newpath: return newpath
    return None

def find_all_paths(G, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if start not in G:
        return []
    paths = []
    for node in G[start]:
        if node not in path:
            newpaths = find_all_paths(G, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)

    return paths

def path_length(G, path):
    len_path = []
    for i in range(len(path) - 1):
        a = (G.get_edge_data(path[i], path[i+1]))
        try:
            len_path.append(a[0]['weight'])
        except:
            continue
    return sum(len_path)

paths = (find_all_paths(G, 0, 6))

for p in paths:
    ret = path_length(G, p)
    p.append(ret)

print(paths)