Модуль: Алгоритм Флойда


Задача

4 /10


Самый короткий путь

Теория Нажмите, чтобы прочитать/скрыть

Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла неприменим к такому графу.

На самом же деле, для тех пар вершин i и j, между которыми нельзя зайти в цикл отрицательного вес, алгоритм отработает корректно.

Для тех же пар вершин, ответа для которых не существует (по причине наличия отрицательного цикла на пути между ними), алгоритм Флойда найдёт в качестве ответа какое-то число (возможно, сильно отрицательное, но не обязательно). Тем не менее, можно улучшить алгоритм Флойда, чтобы он аккуратно обрабатывал такие пары вершин и выводил для них, например, \(- \infty\).

Для этого можно сделать, например, следующий критерий "не существования пути". Итак, пусть на данном графе отработал обычный алгоритм Флойда. Тогда между вершинами i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется \(d[t][t]<0\).

Кроме того, при использовании алгоритма Флойда для графов с отрицательными циклами следует помнить, что возникающие в процессе работы расстояния могут сильно уходить в минус, экспоненциально с каждой фазой. Поэтому следует принять меры против целочисленного переполнения, ограничив все расстояния снизу какой-нибудь величиной (например, \(- \infty\)).

Словесно решение можно описать таким образом:
После того, как алгоритм Флойда-Уоршелла отработает для входного графа, переберём все пары вершин \((i,j)\), и для каждой такой пары проверим, бесконечно мал кратчайший путь из i в j или нет. Для этого переберём третью вершину t, и если для неё оказалось \(d[t][t] < 0\) (т.е. она лежит в цикле отрицательного веса), а сама она достижима из i и из неё достижима j — то путь \((i,j)\) может иметь бесконечно малую длину.

Задача

Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю, стремящийся к бесконечности).
 
Входные данные
В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.
 
Выходные данные
Выведите одно число – искомый минимум. Если его не существует, выведите  -1.
Примеры
Входные данные Выходные данные
1
3
0 42 18468 
6335 0 26501 
19170 15725 0 
42
2
3
0 -7 3
-2 0 10
2 215 0 
-1



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6447
Python17
Комментарий учителя