Статья Автор: Кононенко Дмитрий

графы 23

dist, vert = {}, set() #создаем словарь расстояний от вершины до вершины, множество связанных вершин
x, y = '1', '100'
for s in open('/home/student/Загрузки/demo_23.txt'):
    a,b,d = s.split()
    dist[(a,b)] = float(d)
    vert.add(a)
    vert.add(b)
k=1
n = []
while k>0:
    k=0
    for b in vert:
        edge = [(a,c) for a in vert for c in vert if ((a,b) in dist) and ((b,c) in dist)] #заполняем список существующих ребер с альт путями(в тетради есть картинка)
        for a,c in edge:
            d=dist[(a,b)]+dist[(b,c)]
            if (a,c) not in dist or d<dist[(a,c)]:
                dist[(a,c)] = d
                k+=1
                if (x,y) == (a,c):
                    print(f'{dist[(x,y)]=}')

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать