import random
import heapq

# Создаем случайный граф
graph = {i: {} for i in range(1, 12)}
for v in [2, 3, 4]:
    graph[1][v] = random.randint(1, 10)
for i in range(2, 12):
    for j in range(i + 1, 12):
        if random.random() < 0.3:
            graph[i][j] = graph[j][i] = random.randint(1, 10)

print("Граф:")
print(graph)

def dijkstra(graph, start, end):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    visited = set()
    queue = [(0, start)]
    path = {}

    while queue:
        (current_distance, current_vertex) = heapq.heappop(queue)
        if current_vertex == end:
            # Формируем путь в обратном порядке
            path_list = [end]
            while end != start:
                path_list.append(path[end])
                end = path[end]
            path_list.reverse()
            return (path_list, distances[current_vertex])
        if current_vertex in visited:
            continue
        visited.add(current_vertex)

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                path[neighbor] = current_vertex
                heapq.heappush(queue, (distance, neighbor))
        print("Текущая вершина:", current_vertex)
        print("Длины путей до вершин:", distances)
        print("Предшественники вершин:", path)
        print()

    return (path, distances[end])

# Запускаем алгоритм Дейкстры
print("Решение:")
path, distance = dijkstra(graph, 1, 11)
print("Путь:", path)
print("Длина пути:", distance)

# Создаем матрицу смежности из графа
matrix = [[0] * 11 for _ in range(11)]
for i in range(1, 12):
    for j, weight in graph[i].items():
        matrix[i - 1][j - 1] = weight

# Выводим матрицы
print("Матрица смежности:")
for row in matrix:
    print(row)
print()

print("Матрицы для блочных узлов:")
for i in range(1, 5):
    block_matrix = [[0] * 3 for _ in range(3)]
    for j in range(3):
        for k in range(3):
            block_matrix[j][k] = matrix[(i-1)*3+j][(i-1)*3+k]
    print("Блочная матрица", i, ":")
    for row in block_matrix:
        print(row)
    print()