e-olymp 976. Флойд — существование

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

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

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

   Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути.
  • Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

 

link

Related Images: