Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими)

def BFS(d_edg, start, finish):
    #==========================================================================
    def get_neighbours(d_edg, node):
        res = []
        for key in d_edg:
            if node in key:
                node_ind = key.index( node )
                res.append( ( key[not node_ind], d_edg[key] ) )
        return res
    # ==========================================================================
    if start == finish:
        print('Старт совпадает с финишем.')
        return
    res     = None
    visited = []
    queue   = [ ([start],0) ]
    while queue:
        path, dist = queue.pop(0)
        node       = path[-1]
        if node not in visited:
            neighbours = get_neighbours(d_edg, node)
            for nb_city, nb_dist in neighbours:
                cur_path = path.copy()
                cur_path.append(nb_city)
                cur_dist = dist + nb_dist
                queue.append( (cur_path, cur_dist) )
 
                if nb_city == finish:
                    if not res or cur_dist < res[1]:
                        res = (cur_path, cur_dist)
            visited.append(node)
    if res:
        print( f'Кратчайший путь: ( { " -> ".join(res[0]) } ) = { res[1] } км' )
    else:
        print('Такого пути нет.')
#==============================================================================
d_edg = {
    ( 'петербург',      'горький'       ):      200,
    ( 'петербург',      'москва'        ):      150,
    ( 'москва',         'горький'       ):      100,
 
    ( 'москва',         'саратов'       ):      110,
    ( 'москва',         'ульяновск'     ):      100,
    ( 'горький',        'ульяновск'     ):      50,
 
    ( 'горький',        'свердловск'    ):      300,
    ( 'ульяновск',      'саратов'       ):      50,
    ( 'ульяновск',      'куйбышев'      ):      30,
 
    ( 'саратов',        'куйбышев'      ):      60,
    ( 'саратов',        'магнитогорск'  ):      200,
    ( 'куйбышев',       'свердловск'    ):      150,
 
    ( 'куйбышев',       'магнитогорск'  ):      90,
    ( 'свердловск',     'магнитогорск'  ):      80,
    ( 'свердловск',     'омск'          ):      80,
 
    ( 'магнитогорск',   'омск'            ):    90
}
BFS(d_edg, 'петербург', 'омск')
BFS(d_edg, 'петербург', 'магнитогорск')

def BFS( d_edg, start, finish ):
    # ==========================================================================
    def get_neighbours(d_edg, node):
        res = []
        for key in d_edg:
            if node in key:
                node_ind = key.index(node)
                res.append( (key[not node_ind], d_edg[key]) )
        return res
    # ==========================================================================
    if start == finish:
        print('Старт совпадает с финишем.')
        return
    res   = []
    queue = [ ([start], 0) ]
    while queue:
        path, dist = queue.pop(0)
        if res and dist > res[0][1]:
            continue
        node = path[-1]
        neighbours = get_neighbours(d_edg, node)
        for nb_city, nb_dist in neighbours:
            if nb_city not in path:
                cur_path = path.copy()
                cur_path.append(nb_city)
                cur_dist = dist + nb_dist
                if res and cur_dist > res[0][1]:
                    continue
                queue.append( (cur_path, cur_dist) )
                if nb_city == finish:
                    if not res or cur_dist < res[0][1]:
                        res.clear()
                        res.append( (cur_path, cur_dist) )
                    elif cur_dist == res[0][1]:
                        res.append( (cur_path, cur_dist) )
    if res:
        print()
        print('Кратчайшие пути:')
        for path, dist in res:
            print(f'( { " -> ".join(path) } ) = { dist } км')
    else:
        print('Такого пути нет.')
# ==============================================================================
d_edg = {
    ('петербург',   'горький'       ):  200,
    ('петербург',   'москва'        ):  150,
    ('москва',      'горький'       ):  100,
 
    ('москва',      'саратов'       ):  110,
    ('москва',      'ульяновск'     ):  100,
    ('горький',     'ульяновск'     ):  50,
 
    ('горький',     'свердловск'    ):  300,
    ('ульяновск',   'саратов'       ):  50,
    ('ульяновск',   'куйбышев'      ):  30,
 
    ('саратов',     'куйбышев'      ):  60,
    ('саратов',     'магнитогорск'  ):  200,
    ('куйбышев',    'свердловск'    ):  150,
 
    ('куйбышев',    'магнитогорск'  ):  90,
    ('свердловск',  'магнитогорск'  ):  80,
    ('свердловск',  'омск'          ):  80,
 
    ('магнитогорск', 'омск'         ):  90
}
 
BFS(d_edg, 'петербург', 'омск')
BFS(d_edg, 'петербург', 'магнитогорск')