Статья Автор: Лебедев Дмитрий Алексеевич

Знакомство с заданием 23

Задание выполняется с использованием прилагаемых файлов

В текстовом файле задан ориентированный взвешенный граф, не содержащий циклов. Каждая строка описывает одно ребро и содержит три числа: L, M и W. Натуральные числа L и M — номера начальной и конечной вершин ребра, положительное вещественное число W — его вес. Между одной и той же парой вершин не бывает нескольких рёбер одного направления.

Найдите кратчайший путь из вершины 7 в вершину 941. Длина пути равна сумме весов входящих в него рёбер. Гарантируется, что хотя бы один такой путь существует.

Номера вершин не превосходят 1000 и могут идти не подряд. Вес каждого ребра не превосходит 10 000. В файле не более 200 строк. Числа разделены пробелами и/или символами табуляции, дробная часть отделена точкой. Строки с количеством вершин или рёбер в файле нет.

В ответе запишите целую часть длины кратчайшего пути.

Пример графа:

Пример содержимого файла для этого графа:

63  941  8.0
7   28   4.6
941 512  1.1
63  28   1.5
7   941  11.6
28  941  3.2
7   63   2.4

Ответ для примера: 7.

Пример имеет иллюстративный характер. Для выполнения задания используйте прилагаемый файл.

Задание на определение кратчайшего пути в ориентированном взвешанном графе.
Предполагается, что веса всех ребер положительны,
Для решения такой задачи существуют специализированные алгоритмы:

Алгоритм Дейкстры
Алгоритм Беллмана - Форда
Флойда - Уоршелла

Учитывая ограничения на данные (небольшое количество ребер, разряженность вершин) применим модификацию алгоритмов в следующей схемке:

Считаем данные и созданим словарь ребер (путей)
Составим список промежуточных вершин (тех, из которых выходят ребра и в которые входят ребра)
Пока есть обновления будем обновлять словарь путей

При решении задания не будем учитывать характер вопроса - будем строить таблицу всех возможных путей.
(пока будем определять длину пути - без восстановления пути)

# Подготовка данных
vv, edge = set(), {} # список вершин (с истоком), список ребер(путей)
for s in open('23_01.txt'):
    a, b, d = s. split()
    edge[(int(a), int(b))] = float(d)
    vv.add(a); vv.add(b)
print(len(vv), len(edge))

Видим, что "активных" вершин немного (в среднем степень каждой вершины четыре)
Для исследования задания, оформим ввод в подпрограмму, и будем отслеживать изменение требуемых значений

def zap(fname):
  for s in open(fname):
    a, b, d = s.split()
    vv.add(int(a)) ; vv.add(int(b))
    edge[(int(a),int(b))] = float(d)
vv, edge = set(), {}
x, y = 7,941 # значения, которые входят в вопрос
zap('23_01.txt')
while 1:
    k = 0 #работаем, пока появились новые данные
    for b in vv: # "подвешиваем" за вершину, которую считаем промежуточной 
        ww = [(a,c) for a in vv for c in vv if (a,b) in edge and (b,c) in edge]
        for a, c in ww : # пробег по всем путям с вершиной b
            d = edge[(a,b)] + edge[(b,c)] # длина пути из a  в c через b
            if not ((a,c) in edge) or edge[(a, c)] > d : # обновление 
                k += 1 
                edge[(a, c)] = d
                if a == x and c == y : print(f'{edge[(x,y)]=}') # "интересная печать"
    if k == 0 : break

Рассмотрим задание из демо-версии
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100.
Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Файл 23_00.txt

def zap(fname):
  for s in open(fname):
    a, b, d = s.split()
    vv.add(int(a)); vv.add(int(b)) 
    edge[(int(a),int(b))] = float(d)
vv, edge = set(), {}
x, y = 1,100 # значения, которые входят в вопрос
zap('23_00.txt')
print(len(vv),len(edge))
while 1:
    k = 0 #работаем, пока появились новые данные
    for b in vv: # "подвешиваем" за вершину, которую считаем промежуточной 
        ww = [(a,c) for a in vv for c in vv if (a,b) in edge and (b,c) in edge]
        for a, c in ww : # пробег по всем путям с вершиной b
            d = edge[(a,b)] + edge[(b,c)] # длина пути из a  в c через b
            if not ((a,c) in edge) or edge[(a, c)] > d : # обновление 
                k += 1 
                edge[(a, c)] = d
                if a == x and c == y : print(f'{edge[(x,y)]=}') # "интересная печать"
    if k == 0 : break
#print(int(edge[(x,y)]))

В целом код несложный, возможно изменение вопроса в следующих модификациях:

самый длинный путь
проходит/ не проходит через данную вершину (решение аналогично заданию 13)
круговое движение из А и В по кратчайшему, обратно по самому длинному
и т.п.

Attached files
23_00.txt
23_01.txt

Печать