Участник:Romanvin/Несложно о сложности. Примеры алгоритмов/Задачи/ex-dijksta-not-work-on-negative-weight

Материал из DISCOPAL
Перейти к: навигация, поиск


Алгоритм Дейкстры является в некотором роде «жадным» — найдя один раз минимальный путь до вершины,

он фиксирует его как минимальный навсегда — поскольку путь через другие вершины не может быть короче найденного.

Но в графе с отрицательными дугами это не так! Рассмотрим такой вот граф, заданный матрицей смежности:

U2IHmaKT4Iw.jpg

Запустим алгоритм Дейкстры из вершины А. На первом шаге у нас будут расстояния до вершин Б и В — 4 и 2 соответственно,

поэтому алгоритм решит, что уже нашел кратчайший путь к вершине В — ведь кратчайший путь к В никак не может идти через Б, не так ли?

С сожалению, не так — очевидно, путь А-Б-В на самом деле короче чем А-В.