"Транспортный" граф

import matplotlib.pyplot as plt
import networkx as nx
 
g = nx.Graph()  #граф
 
# создаем узлы
nodes = [x for x in range(1,21)]
 
# рёбра
edges = [(1, 3), (1, 5), (1, 7), (1, 8), (1, 19),
         (2, 13), (2, 15), (2, 17), (2, 18), (2, 6),
         (3, 1), (3, 15), (3, 4), (3, 20), (3, 11),
         (4, 3), (4, 1), (4, 10), (4, 20), (4, 14),
         (5, 1), (5, 11), (5, 12), (5, 16), (5, 9),
         (6, 1), (6, 15), (6, 14), (6, 9), (6, 17)]
 
# пихаем всё в граф
g.add_nodes_from(nodes)
g.add_edges_from(edges)
 
nb = int(input()) # старт
ne = int(input()) # стоп
 
#все кратчайшие пути
sp = [p for p in nx.all_shortest_paths(g, source=nb, target=ne)]
print(sp, len(sp))
 
#все простые пути
ep = [p for p in nx.all_simple_paths(g, source=nb, target=ne)]
print(ep, len(ep))
 
#все мосты (ребра конечных узлов)
print([p for p in nx.bridges(g)])
 
# рисуем граф и отображаем его
nx.draw(g, with_labels=True, font_weight='bold')
plt.show()

from collections import defaultdict
from itertools import combinations
 
# поиском в глубину выводит все маршруты от start до finish для графа graph
# возможно стоит засунуть внутрь класса, но не хотелось со статикметодами 
# в питоне связываться
def find_all_paths(graph, start, finish):
    def find_all_paths_inner(graph, start, finish, path=[]):
        path = path + [start]
        if start == finish:
            result.append(path)
        if start not in graph:
            return []
        for node in graph[start]:
            if node not in path:
                find_all_paths_inner(graph, node, finish, path)
 
    result = []
    find_all_paths_inner(graph, start, finish)
    return result
 
 
class Network:
    def __init__(self):
        self.graph = defaultdict(list) # сам граф, вершина: [список потомков]
        self.stages = defaultdict(list) # список перегонов, они же ребра. ребро: номер маршрута
        self.routes = dict() # маршрут: список станций в порядке следования
        
    def add_vertice(self, vertice):
        if vertice not in self.graph:
            self.graph[vertice] = []
        
    def add_edge(self, node_from, node_to):
        self.graph[node_from].append(node_to)
        
    def add_route(self, route_number, route):
        self.routes[route_number] = route
        for pair in combinations(route, 2):
            self.stages[pair].append(route_number)
            self.add_edge(*pair)
 
    # проводим поиск в ширину, 
    # результат - граф с узлами кратчайшего пути
    def bfs(self, start, finish):
        visited = {start}
        best_ways = defaultdict(set)
        current = [start]
        while finish not in visited:
            next_step = []
            for node in current:
                for child in self.graph[node]:
                    if child not in visited:
                        next_step.append(child)
                        best_ways[node].add(child)
            visited.update(next_step)
            current = next_step
            if not next_step:
                return []
        return best_ways
                        
    def list_best_path(self, start, finish):
        return find_all_paths(self.bfs(start, finish), start, finish)

mynet = Network()
mynet.add_route(1,[1,2,3,4,5])
mynet.add_route(2,[2,4,6,7,8])
mynet.add_route(3,[1,2,5])
mynet.add_route(4,[6,7,8,9,10])
mynet.add_route(5,[4,7,8,9])
print(*mynet.list_best_path(1,10), sep="\n")

from collections import defaultdict
from itertools import pairwise
 
 
class Network:
    def __init__(self):
        self.graph = defaultdict(list)  # сам граф, вершина: [список потомков]
        self.edges = defaultdict(list)  # список перегонов, они же ребра. ребро: ид ТС
 
 
        # хардкодим сеть
        self.add_transport(1, [("H", "S"), ("B", "V"), ("B", "S"), ("S", "V")])
        self.add_transport(2, [("Z", "V"), ("M", "V"), ("M", "P"), ("P", "V")])
 
    def add_node(self, node):
        if node not in self.graph:
            self.graph[node] = []
            
    def add_edge(self, transport_id, node1, node2):
        self.graph[node1].append(node2)
        self.graph[node2].append(node1)
        self.edges[(node1,node2)].append(transport_id)
        self.edges[(node2, node1)].append(transport_id)
 
    def add_transport(self, transport_id, list_edges):
        for edge in list_edges:
            self.add_edge(transport_id, *edge)
 
 
    # проводим поиск в ширину, 
    # результат - граф с узлами кратчайшего пути
    def bfs(self, start, finish):
        visited = {start}
        best_ways = defaultdict(set)
        current = [start]
        while finish not in visited:
            next_step = []
            for node in current:
                for child in self.graph[node]:
                    if child not in visited:
                        next_step.append(child)
                        best_ways[node].add(child)
            visited.update(next_step)
            current = next_step
            if not next_step:
                return []
        return best_ways
 
    @staticmethod
    # поиском в глубину выводит все маршруты от start до finish для графа graph
    # graph != self.graph
    def find_all_paths(graph, start, finish):
        def find_all_paths_inner(graph, start, finish, path=None):
            if path is None:
                path = []
            path = path + [start]
            if start == finish:
                result.append(path)
            if start not in graph:
                return
            for node in graph[start]:
                if node not in path:
                    find_all_paths_inner(graph, node, finish, path)
 
        result = []
        find_all_paths_inner(graph, start, finish)
        return result
 
    def list_best_path(self, start, finish):
        return Network.find_all_paths(self.bfs(start, finish), start, finish)
 
    def print_route_receipt(self, route):
        print(*route, sep=" -> ")
        for edge in pairwise(route):
            print(f'{edge[0]} -> {edge[1]}: TC №{"№: " if len(self.edges[edge]) > 1 else ""}'
                  f'{", ".join(map(str, self.edges[edge]))}')
        print()

mynet = Network()
 
best_paths = mynet.list_best_path("H", "P")
for path in best_paths:
    mynet.print_route_receipt(path)
 
 
# H -> S -> V -> P
# H -> S: TC №1
# S -> V: TC №1
# V -> P: TC №2

from collections import defaultdict
from itertools import pairwise, product, combinations
 
 
class Network:
    def __init__(self):
        self.graph = defaultdict(set)  # сам граф, вершина: [список потомков]
        self.edges = defaultdict(set)  # список перегонов, они же ребра. ребро: ид ТС
 
        # хардкодим сеть
        self.add_transport(1, product([1], [2, 3, 4, 5]))
        self.add_transport(1, product([2], [7, 8, 9]))
        self.add_transport(1, product([3], [4, 5, 7]))
        self.add_transport(1, product([4], [5]))
        self.add_transport(1, product([6], [8, 9]))
        self.add_transport(1, combinations([7, 8, 9], 2))
        self.add_transport(2, combinations([1, 2, 9, 10, 11], 2))
        self.add_transport(3, product([4], [12, 14]))
        self.add_transport(3, product([6], [9, 15, 18]))
        self.add_transport(3, product([9], [13, 15, 18]))
        self.add_transport(3, product([11], [12, 13, 17, 18]))
        self.add_transport(3, product([12], [16, 17]))
        self.add_transport(3, product([13], [15, 18]))
        self.add_transport(3, product([14], [15]))
        self.add_transport(3, product([16], [17, 19]))
        self.add_transport(3, product([17], [19]))
        self.add_transport(4, [(7, 20), (8, 21), (9, 4)], 1)
        self.add_transport(5, [(7, 22), (8, 20), (9, 14)], 1)
 
    def add_node(self, node):
        if node not in self.graph:
            self.graph[node] = []
 
    def add_edge(self, transport_id, node1, node2, is_orient=0):
        self.graph[node1].add(node2)
        self.edges[(node1, node2)].add(transport_id)
        if not is_orient:
            self.graph[node2].add(node1)
            self.edges[(node2, node1)].add(transport_id)
 
    def add_transport(self, transport_id, edges, is_orient=0):
        for edge in edges:
            self.add_edge(transport_id, *edge, is_orient)
 
    # проводим поиск в ширину,
    # результат - граф с узлами кратчайшего пути
    def bfs(self, start, finish):
        visited = {start}
        best_ways = defaultdict(set)
        current = [start]
        while finish not in visited:
            next_step = []
            for node in current:
                for child in self.graph[node]:
                    if child not in visited:
                        next_step.append(child)
                        best_ways[node].add(child)
            visited.update(next_step)
            current = next_step
            if not next_step:
                return []
        return best_ways
 
    @staticmethod
    # поиском в глубину выводит все маршруты от start до finish для графа graph
    # graph != self.graph
    def find_all_paths(graph, start, finish):
        def find_all_paths_inner(graph, start, finish, path=None):
            if path is None:
                path = []
            path = path + [start]
            if start == finish:
                result.append(path)
            if start not in graph:
                return
            for node in graph[start]:
                if node not in path:
                    find_all_paths_inner(graph, node, finish, path)
 
        result = []
        find_all_paths_inner(graph, start, finish)
        return result
 
    def get_best_path(self, start, finish):
        return Network.find_all_paths(self.bfs(start, finish), start, finish)
 
    def print_route_receipt(self, route):
        print(*route, sep=" -> ")
        for edge in pairwise(route):
            print(f'{edge[0]} -> {edge[1]}: TC №{"№: " if len(self.edges[edge]) > 1 else ""}'
                  f'{", ".join(map(str, self.edges[edge]))}')
        print()

mynet = Network()
best_paths = mynet.get_best_path(1, 21)
for path in best_paths:
    mynet.print_route_receipt(path)