import random as rd

def Dis_generate(nums, n_min, n_max):

    return [[int((n_max-n_min) * rd.random() + n_min) if i != j else 0 for j in range(nums)] for i in range(nums)]

def Dijkstra(Dis):

    n = len(Dis)

    R = []
    Dis_R = []

    for start in range(n):
        #使用状态、路线、距离
        states = [0 if i != start else 1 for i in range(n)]
        r = ["" if i != start else str(start) for i in range(n)]
        dis = [Dis[start][i] for i in range(n)]

        while sum(states) < n:
            S1 = [i for i in range(n) if states[i] == 1]
            S2 = [i for i in range(n) if states[i] == 0]
            temp = [[dis[i] + Dis[i][j] for j in S2] for i in S1]
            mid, end = S1[0], S2[0]
            for i in S1:
                for j in S2:
                    if dis[i] + Dis[i][j] < dis[mid] + Dis[mid][end]:
                        mid, end = i, j
            states[end] = 1
            r[end] = r[mid] + "-" + str(end)
            dis[end] = dis[mid] + Dis[mid][end]

        R.append(r)
        Dis_R.append(dis)
    return R, Dis_R

def sub_LL_print(L, digit):
    s = "["
    for i in range(len(L)):
        s = s + str(L[i])
        temp = L[i]
        digit_temp = 1
        while temp//10>0:
            digit_temp += 1
            temp = temp//10
        for j in range(digit-digit_temp):
            s += " "
        if i < len(L)-1:
            s += ",  "
    s += "]"
    return s

def LL_print(name, LL):
    LL1 = [[int(LL[i][j]) for j in range(len(LL[i]))] for i in range(len(LL))]
    num_max = max([max(LL1[i]) for i in range(len(LL1))])
    digit = 1
    while num_max//10>0:
        digit += 1
        num_max = num_max // 10

    print("\n",name+":")
    print("["+sub_LL_print(LL[0], digit)+",")
    for i in range(1,len(LL)-1):
        print(" "+sub_LL_print(LL[i], digit)+",")
    print(" " + sub_LL_print(LL[-1], digit) + "]")

def sub_LL_print_str(L, digit):
    s = "["
    for i in range(len(L)):
        s = s + L[i]
        temp = L[i]
        digit_temp = len(L[i])
        for j in range(digit-digit_temp):
            s += " "
        if i < len(L)-1:
            s += ",  "
    s += "]"
    return s

def LL_print_str(name, LL):
    digit = max([max([len(LL[i][j]) for j in range(len(LL[i]))]) for i in range(len(LL))])
    print("\n",name+":")
    print("["+sub_LL_print_str(LL[0], digit)+",")
    for i in range(1,len(LL)-1):
        print(" "+sub_LL_print_str(LL[i], digit)+",")
    print(" " + sub_LL_print_str(LL[-1], digit) + "]")

if __name__ == "__main__":

    #点的个数
    nums = 100
    #点集生成
    Dis = Dis_generate(nums, 1, 100)
    LL_print("Dis", Dis)
    #路线及对应距离
    R, Dis_R = Dijkstra(Dis)
    LL_print_str("R", R)