Оптимизация в булевозначных сетях

Под булевозначной сетью понимается ориентированный мультиграф, каждой дуге которого приписан некоторый элемент из фиксированной конечной булевой алгебры $B$. Объединение меток всех дуг вдоль данного пути называется оценкой этого пути, а число атомов булевой алгебры $B$, содержащихся в оценке, – разнообразием пути. Путь $(s,t)$ из начальной вершины $s$ в назначенную вершину $t$ по определению является оптимальным, если он имеет наименьшее возможное для $(s,t)$-путей разнообразие и среди $(s,t)$-путей с таким же разнообразием имеет наименьшую длину (число составляющих дуг). В заметке предлагается алгоритм, позволяющий за время $O(n^3)$ найти один из оптимальных $(s,t)$-путей в $n$-вершинной $B$-сети.