DIjkstra 1

import networkx as nx

G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
G.add_edges_from([(1, 2, {'weight': 13}), (1, 4, {'weight': 17}), (1, 7, {'weight': 19}), (1, 10, {'weight': 19}),
                  (1, 12, {'weight': 4})])
G.add_edges_from([(2, 1, {'weight': 13}), (2, 3, {'weight': 18}), (2, 4, {'weight': 9}), (2, 9, {'weight': 9})])
G.add_edges_from([(3, 2, {'weight': 18}), (3, 4, {'weight': 20}), (3, 5, {'weight': 5})])
G.add_edges_from([(4, 1, {'weight': 17}), (4, 2, {'weight': 9}), (4, 3, {'weight': 20})])
G.add_edges_from([(5, 3, {'weight': 5}), (5, 6, {'weight': 7}), (5, 11, {'weight': 20}), (5, 12, {'weight': 11})])
G.add_edges_from([(6, 5, {'weight': 7}), (6, 7, {'weight': 4}), (6, 12, {'weight': 3})])
G.add_edges_from([(7, 1, {'weight': 19}), (7, 6, {'weight': 4}), (7, 8, {'weight': 8}), (7, 12, {'weight': 18})])
G.add_edges_from([(8, 7, {'weight': 8}), (8, 10, {'weight': 3}), (8, 11, {'weight': 10})])
G.add_edges_from([(9, 2, {'weight': 2}), (9, 10, {'weight': 16}), (9, 11, {'weight': 14})])
G.add_edges_from([(10, 1, {'weight': 19}), (10, 8, {'weight': 3}), (10, 9, {'weight': 16}), (10, 11, {'weight': 12})])
G.add_edges_from([(11, 5, {'weight': 20}), (11, 8, {'weight': 10}), (11, 9, {'weight': 14}), (11, 10, {'weight': 12})])
G.add_edges_from([(12, 1, {'weight': 4}), (12, 5, {'weight': 11}), (12, 6, {'weight': 3}), (12, 7, {'weight': 18})])
# TODO: проверить, что будет, если вводить не полностью все рёбра, а только половину (верхнюю часть м-цы смежности)

degrees = list(nx.degree(G))  # Получаем список из упорядоченных пар (вершина, степень)
vertexes = []
for i in range(0, len(degrees)):  # Ищем вершины с нечётными степенями
    if degrees[i][1] % 2 == 1:
        vertexes.append(degrees[i][0])

for i in vertexes:  # Добавляем в граф H кратчайшие пути между его вершинами
    for j in vertexes:
        if i != j:
            print('Path from', i, 'to', j, ':', nx.single_source_dijkstra(G, i, j, weight='weight'))