| |
|
|
| | Имеется направленный граф (вроде не путаю термины - набор точек, соединённых отрезками с началом и концом). В этом графе имеются две произвольные точки, не совпадающие друг с другом. Требуется найти все возможные пути от одной точки к другой с учётом направлений рёбер.
Дополнительные условия:
- каждая вершина принадлежит как минимум двум рёбрам;
- для каждой вершины есть и "входящие" и "выходящие" рёбра;
- количество вершин имеет порядок десятков (то есть их не больше сотни-двух).
То есть по сути это электрическая схема, к двум точкам которой приложена разность потенциалов, и нужно найти все возможные пути протекания наибольшего тока - как в нормальном режиме, так и при разрыве цепи в любой точке или точках.
Теорию графов не изучал, так что ничего умнее перебора не придумал; но даже в первых прикидках число вариантов выходит несуразно большим. Есть ли какие-то более оптимальные пути? Или хотя бы какой-то алгоритм перебора, позволяющий уложиться в более-менее разумные рамки по затрате ресурсов? | |
| |
|
