Цитата: kemerover от августа 25, 2021, 01:541. Сам алгоритм Форда-Беллмана не детектирует отрицательные циклы. Он за n-1 итерацию формирует вектор расстояний. Если к нему что-то ещё дописать, тогда, конечно, будет. Есть такая вещь, называется корректная математическая постановка. Вот для Ф.-Б. она звучит так: задан орграф без контуров отрицательного веса и вершина-источник. Результат работы: вектор расстояний от источника до всех вершин графа.Цитата: _Swetlana от августа 25, 2021, 00:44Вроде алгоритм Беллмана — Форда детектирует отрицательные циклы и отлично с ними справляется. Если же надо найти кратчайший простой путь (то есть, в котором каждая вершина встречается максимум один раз), то тут он не подойдёт, но это и задача другая.
Неправда.
Все алгоритмы (кроме поиска в ширину на невзвешенном графе) работают с ОРГРАФАМИ.
И не все эти алгоритмы переносятся на неориентированные графы. Это связано с тем, что при расщеплении неориентированного ребра на пару противоположно направленных дуг образуется орцикл. Если ребро имело отрицательный вес, то образуется контур отрицательного веса. Таким образом, на неориентированные графы переносится только алгоритм Дейкстры. А алгоритмы Форда-Беллмана и Флойда применимы только для неор. графов без отрицательных весов.
Цитата: _Swetlana от августа 25, 2021, 00:44Вроде алгоритм Беллмана — Форда детектирует отрицательные циклы и отлично с ними справляется. Если же надо найти кратчайший простой путь (то есть, в котором каждая вершина встречается максимум один раз), то тут он не подойдёт, но это и задача другая. Для неё вроде каких-то классических алгоритмов нету, разве что перебором решать или лезть в какие-то учебники и журналы.
Неправда.
Все алгоритмы (кроме поиска в ширину на невзвешенном графе) работают с ОРГРАФАМИ.
И не все эти алгоритмы переносятся на неориентированные графы. Это связано с тем, что при расщеплении неориентированного ребра на пару противоположно направленных дуг образуется орцикл. Если ребро имело отрицательный вес, то образуется контур отрицательного веса. Таким образом, на неориентированные графы переносится только алгоритм Дейкстры. А алгоритмы Форда-Беллмана и Флойда применимы только для неор. графов без отрицательных весов.
Цитата: Karakurt от августа 24, 2021, 22:58Самый простой - алгоритм Флойда. Кроме тройного цикла там ничего нет. И граф хранится в двумерном массиве весов.
Какой алгоритм проще?
(wiki/ru) Задача_о_кратчайшем_пути#%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B
Цитата: kemerover от августа 24, 2021, 23:25Неправда.
Все эти алгоритмы могут работать с ориентированными и неориентированными графами.
Цитата: Karakurt от августа 24, 2021, 22:58Если граф не взвешенный, то поиск в ширину. Если граф взвешенный, то Дейкстра. Если граф взвешенный с возможными отрицательными рёбрами, то Беллман — Форд. Все эти алгоритмы могут работать с ориентированными и неориентированными графами.
Какой алгоритм проще?
(wiki/ru) Задача_о_кратчайшем_пути#%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B
Страница создана за 0.052 сек. Запросов: 23.