import math
import random
def graph_generator(n, mean_degree, max_weight):
    if mean_degree < 2 * (n - 1) / n:
        mean_degree = 2 * (n - 1) / n
    if mean_degree > n - 1:
        mean_degree = (n - 1)
    num_of_edges = int(mean_degree * n / 2)
    W = []
    for i in range(n):
        W.append(['-'] * n)
        W[i][i] = 0
    stack = []
    for i in range(n):
        stack.append(i)
    random.shuffle(stack)
    while stack:
        first = stack.pop()
        if stack:
            second = random.choice(stack)
            W[first][second] = W[second][first] = random.randint(1, max_weight)
    edges_not_tree = num_of_edges - (n - 1)
    for _ in range(edges_not_tree):
        first = random.randint(0, n - 1)
        second = random.randint(0, n - 1)
    W[first][second] = W[second][first] = random.randint(1, max_weight)
    return W
def to_inf(W):
    for i in range(len(W)):
        for j in range(len(W)):
            if D[i][j] == '-' or D[i][j] == 0:
                D[i][j] = math.inf
    return W
def arg_min(T, S):
    amin = -1
    m = math.inf  # максимальное значение
    for i, t in enumerate(T):
        if t < m and i not in S:
            m = t
            amin = i
    return amin
D2 = graph_generator(3, 1, 3)
D = [[0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 5, 8],
     [0, 0, 6, 0, 0, 8, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 5, 0, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 3, 0, 6, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 5, 3, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 6, 0, 0],
     [0, 0, 0, 0, 0, 1, 0, 0, 8, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 6],
     [0, 3, 6, 0, 0, 4, 0, 0, 2, 0, 0, 0]]
to_inf(D)
def dijkstra(D, start, end):
    Nodes = len(D)
    Distance = [math.inf] * Nodes
    starting_node = 0
    visited = {starting_node}
    Distance[starting_node] = 0
    count = 0
    optimal_links = [0] * Nodes
    while starting_node != -1:
        for j, dw in enumerate(D[starting_node]):
            if j not in visited:
                w = Distance[starting_node] + dw
                if w < Distance[j]:
                    Distance[j] = w
                    optimal_links[j] = starting_node
        starting_node = arg_min(Distance, visited)
        if starting_node >= 0:
            visited.add(starting_node)
    Path = [end]
    count += end
    while end != start:
        end = optimal_links[Path[-1]]
        Path.append(end)
    print("Путь из вершины ", start, ":", Path[::-1])
    print("Длина кратчайшего пути: ", Distance[count])
dijkstra(D, 0, 5)