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))

    return (path, distances[end])

# Находим кратчайший путь от вершины 1 до вершины 11
path, distance = dijkstra(graph, 1, 11)
print("Кратчайший путь:", path)
print("Длина пути:", distance)