Hазрела у меня следущая задачка...
Hа входе есть разнообразные пути следования по вершинам графа в виде
a->b
a->b->c
d->e->f
и так далее.
количество этих путей (маршрутов) жестко фиксировано и сами они жестко
определены.
По условиям задачи, следует компактизировать этот ориентированный граф
(т.е. выполнить декомпозицию всех этих путей прохода вида a->b, d->e->f.. итд)
в виде нескольких ориентированных, но _уже_взвешенных_ графов, чтобы потом
суметь _однозначно_ восстановить какой-то из изначальных путей алгоритмом
Дейкстры. Дело в том что Дейкстра будет работать на одном из маленьких графов
быстрее. Предлагается ввести список соответсвия, в каком из получившихся графов
искать Дейкстрой путь. (Таких графов для данного пути может быть не один).
То есть понимаете что получается.
Все сложные пути вида a->b->c->d->e->f мы декомпозируем в несколько небольших
более простых графов, и восстанавливаем исходный путь поиском при помощи
Дейкстры (для этого нужно расставить в графах веса). Причем важное условие.
Hужно восстанавливать не все _возможные_ пути и подпути, нет. Hужно
восстанавливать пути as is, также как они были на входе. Что было, то
восстановилось Дейкстрой. Укзали в табличку "найди путь между d и f, ищи в
графе X" - Дейкстра поискал и восстановил путь d->e->f, так как в данном графе
веса расставлены именно так, что находится именно такой путь. Это очень важно
уметь вычленить все изначальные пути что были на входе. Выжным дополнительным
условием составления алгоритма является минимизация (оптимизация) кол-ва графов
на выходе.
Хотелось бы услышать, что делать. Или названия алгоритмов, "попробуй это"
keywords, советы итд.