Графики: выяснить, если путь хотя бы на X% лучше других

Question

Предположим, у нас есть путь в неориентированном циклическом взвешенном графе.Предполагая, что у нас есть механизм, который может найти путь от узла A к узлу B в таком графе, есть ли простой способ / алгоритм, чтобы выяснить, является ли данный путь от A до B по крайней мере на X% лучше, чем любой другой непересекающийся путьОт а до б?Под дизъюнктом я подразумеваю, что два пути не могут иметь общих ребер.

Answer 1

Единственный способ сделать это - удалить ребра заданного пути из графика, найти путь минимального веса от A до B на меньшем графике и сравнить.

Чтобы решить эту проблему, используя этот подход, попробуйте один из этих хорошо изученных алгоритмов:

• Алгоритм Дейкстры решает проблемы кратчайшего пути из одного источника.
• Алгоритм Беллмана-Форда решает проблему с одним источником, если вес ребер может быть отрицательным.
• Алгоритм поиска * решает для одной пары кратчайший путь, используя эвристику, чтобы попытаться ускорить поиск.
• Алгоритм Флойда-Варшалла решает все пары кратчайших путей.
• Алгоритм Джонсона решает все пары кратчайших путей и может быть быстрее, чем Флойд-Варшалл на разреженных графах.
• Теория возмущений находит (в худшем случае) локально кратчайший путь.