Статья Автор: Деникина Н.В., Деникин А.В.

Кратчайший путь в графе из файла — Отрицательные веса

Чего мы не взяли и почему

Есть третий известный алгоритм — Дейкстра. Его знают все, и на этом задании он тоже работает. Но в наш модуль он не попал, и стоит объяснить, почему.

Как устроена Дейкстра

Она берёт вершину с наименьшим рекордом и объявляет его окончательным: короче до неё уже не будет. Потом раздаёт улучшения соседям и переходит к следующей ближайшей.

Рассуждение держится на том, что все веса положительные — любой обходной путь только прибавляет к сумме.

Где она ломается

Появилось хоть одно отрицательное ребро — и в закрытую вершину можно вернуться дешевле. Но она закрыта, и Дейкстра туда не вернётся.

Дейкстра закрывает вершину навсегда — в этом её слабое место.

Форд–Беллман не закрывает ничего. Улучшение может прийти хоть на сотом проходе, и он его примет. Флойд тоже спокойно переживает отрицательные веса.

Что при этом не меняется

Программа из третьей тетради остаётся ровно той же, ни одной новой строки. Отрицательные веса Форду–Беллману просто не мешают.

Кратчайшего пути не существует лишь в одном случае: если по кругу можно пройти и стать дешевле. Но круг — это цикл, а в нашем графе циклов нет по условию, так что проверять нечего.

Как Дейкстра работает, пока веса положительные

Золотое кольцо — вершина обработана, её рекорд больше не изменится. На шагах 3 и 4 заметь: рекорд сотни переписывается дважды, пока её саму не взяли в обработку.

◀◀◀◀◀◀◀◀▶▶▶▶▶▶▶▶▶ показать всё▮▮ стопшаг 1 из 6 · стартшаг 2 из 6 · берём 1шаг 3 из 6 · берём 4шаг 4 из 6 · берём 7шаг 5 из 6 · берём 100шаг 6 из 6 · берём 12идёт показ…

Золотое кольцо — вершина обработана, её рекорд уже не изменится.

Граф, на котором Дейкстра врёт

Четыре вершины, одно отрицательное ребро. Запустим на нём Дейкстру и Форда–Беллмана подряд.

data = []
for s in open("neg_demo.txt"):
    v1, v2, w = s.split()
    data.append((int(v1), int(v2), float(w)))

print(data)

INF = float('inf')
dist = [INF] * 1001                          # Дейкстра
dist[1] = 0
used = []
while True:
    v = -1
    for x in range(1001):
        if dist[x] < INF and x not in used:
            if v == -1 or dist[v] > dist[x]:
                v = x
    if v == -1:
        break
    used.append(v)
    for i, j, w in data:
        if i == v:
            dist[j] = min(dist[j], dist[v] + w)

print("Дейкстра:", dist[100])

d2 = [INF] * 1001                            # Форд-Беллман
d2[1] = 0
for step in range(1000):
    for i, j, w in data:
        d2[j] = min(d2[j], d2[i] + w)

print("Форд-Беллман:", d2[100])

Что печатает демонстрация

[(1, 7, 2.0), (1, 4, 5.0), (4, 7, -4.0), (7, 100, 1.0)]
Дейкстра: 3.0
Форд-Беллман: 2.0

Дейкстра взяла вершину 7 с рекордом 2.0 и закрыла её. Потом дошла до вершины 4 и увидела ребро весом −4.0: через него до семёрки было бы всего 1.0, а до сотни 2.0. Но семёрка уже закрыта, и рекорд сотни остался 3.0.

Форд–Беллман ничего не закрывал и на следующем проходе спокойно нашёл 2.0.

Что делает каждая строка основной программы

строка	что делает
`used.append(v)`	Дейкстра закрывает вершину — сюда она больше не вернётся
`for step in range(1000)`	Форд–Беллман не закрывает ничего и проходит список заново
`min(dist[j], dist[i] + w)`	строка улучшения не меняется: минус в весе ей безразличен
`float(w)`	минус разбирается сам, отдельной обработки не нужно

data = []
for s in open("negA.txt"):
    v1, v2, w = s.split()                    # split() режет по любым пробелам и табуляциям
    data.append((int(v1), int(v2), float(w)))

INF = float('inf')
dist = [INF] * 1001                          # dist[v] - рекорд: кратчайший путь из 1 в v
dist[1] = 0                                  # до самой единицы идти не надо

for step in range(1000):                     # вершин не больше 1000, проходов хватит
    for i, j, w in data:
        dist[j] = min(dist[j], dist[i] + w)

print(dist[100])
print(int(dist[100] + 0.000001))

Что печатает программа

5.1999999999999975
5

Это дословно программа из третьей тетради, в ней не изменено ни одного символа. Четырнадцать рёбер из тридцати четырёх отрицательные, и она этого даже не заметила.

Длина пути вышла положительной, хотя веса в основном отрицательные. Так и задумано: у отрицательных чисел целая часть считается вниз, и вопрос «целая часть от −5.2» превратился бы в спор о терминах.

Ловушки

Взяли Дейкстру, потому что она быстрее. С отрицательным ребром она молча выдаёт неверное число.
Начали переписывать Форда–Беллмана под отрицательные веса. Он и так работает, менять нечего.
Решили, что при отрицательных весах кратчайшего пути может не быть. В ациклическом графе он есть всегда.
Забыли, что целая часть отрицательного числа считается вниз.

Граф-контрпример: целая часть длины кратчайшего пути из вершины 1 в вершину 100.

Проверить ответ

Файл negA.txt: целая часть длины кратчайшего пути из вершины 1 в вершину 100.

Проверить ответ

По графу-контрпримеру отметьте, что верно.

Проверить ответ

Загрузка...

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

💬

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

Печать