лучший путь для дизайна канализации

Question

Существует ли какой-либо алгоритм (ы), который может найти все пути между источником и приемником в данном связанном, неориентированном, взвешенном графе / сети?Сеть состоит из нескольких исходных узлов и одного приемного узла.Путь не должен содержать петель

Answer 1

Я бы подошел к этому алгоритму A * со следующими отличиями от базового поиска пути.

• Начните с приемника, а не с источника, так как имеется только один приемник
• Каждый узел представляет собой набор позиций, а не одну позицию. В каждой итерации добавляйте соседей всех позиций в очередь. Также создайте ветки для всех соседей так, чтобы в следующем наборе была еще одна позиция. Ограничьте максимальное количество позиций количеством источников в качестве оптимизации.
• Отслеживайте, какие источники вы достигли на каждом пути
• Функция пройденной стоимости должна быть общим пройденным расстоянием со всеми объединенными разветвленными путями
• Функция оценки должна объединять все оставшиеся источники

Это должно дать оптимальные пути, если алгоритм A * используется правильно.

Answer 2

Это похоже на Минимальное остовное дерево .

Answer 3

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