Лингвофорум

Цитата: kemerover от августа 25, 2021, 01:54

Цитата: _Swetlana от августа 25, 2021, 00:44
Неправда.
Все алгоритмы (кроме поиска в ширину на невзвешенном графе) работают с ОРГРАФАМИ.
И не все эти алгоритмы переносятся на неориентированные графы. Это связано с тем, что при расщеплении неориентированного ребра на пару противоположно направленных дуг образуется орцикл. Если ребро имело отрицательный вес, то образуется контур отрицательного веса. Таким образом, на неориентированные графы переносится только алгоритм Дейкстры. А алгоритмы Форда-Беллмана и Флойда применимы только для неор. графов без отрицательных весов.

Вроде алгоритм Беллмана — Форда детектирует отрицательные циклы и отлично с ними справляется. Если же надо найти кратчайший простой путь (то есть, в котором каждая вершина встречается максимум один раз), то тут он не подойдёт, но это и задача другая.

1. Сам алгоритм Форда-Беллмана не детектирует отрицательные циклы. Он за n-1 итерацию формирует вектор расстояний. Если к нему что-то ещё дописать, тогда, конечно, будет. Есть такая вещь, называется корректная математическая постановка. Вот для Ф.-Б. она звучит так: задан орграф без контуров отрицательного веса и вершина-источник. Результат работы: вектор расстояний от источника до всех вершин графа.
То есть вначале проверь граф на наличие отрицательных контуров, а затем запускай поиск кратчайшего пути.
С отрицательными контурами работает один-единственный алгоритм дефекта, который строит в сети циркуляцию минимальной стоимости. И этот контур с отрицательной стоимостью должен иметь ограниченную пропускную способность.
 
2. Форд-Беллман автоматически находит простые пути без циклов. Потому что в орграфе, с которым он может работать, все контуры имеют положительный вес. Добавление к пути контура положительного веса его удлиняет, поэтому кратчайший путь, найденный Ф.-Б., автоматически не содержит контуров, т.е. в нём нет повторяющихся вершин.
А вот с контурами нулевого веса, как я уже говорила, есть определённые проблемы. Но эти проблемы возникают не на этапе генерации вектора расстояний от источника до всех остальных вершин, а на этапе восстановления пути.

Мне, оказывается, нужно было такое:



Есть кучка муравьев, нужно чтобы они как можно быстрее дошли до конца. Алгоритм - поиск в ширину.

Цитата: _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

Если граф не взвешенный, то поиск в ширину. Если граф взвешенный, то Дейкстра. Если граф взвешенный с возможными отрицательными рёбрами, то Беллман — Форд. Все эти алгоритмы могут работать с ориентированными и неориентированными графами.

Какой алгоритм проще?
(wiki/ru) Задача_о_кратчайшем_пути#%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B

Как доказать, что для любого нерационального элемента поля Q[x₁,x₂,...,x_n] всегда существует изменяющая его перестановка иксов???

Кроме этой фигни все теорию Галуа реконструировал. Эта хрень ну никак не дается. В принципе это самая суть и самое сложное в теории Галуа. У нее нетривиальные следствия. Например, если x₁x₂+x₃x₄ рационально, то вообще любое f(x₁)f(x₂)+f(x₃)f(x₄) тоже рационально.

(Да, а толщина кружек для пробных отливок примерно такая же, как у рабочих форм? Если нет, то задача радикально усложняется, и вообще не факт, что практически разрешима).