Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)
3:45p
Графы Помогите, пожалуйста, придумать алгоритм (полный перебор не подходит).
Есть ориентированный граф, в котором выделены 2 вершины - s и t. Длина каждого ребра графа - положительная целая величина. Пусть l(P) - длина пути P от вершины s к вершине t. Требуется найти два пути P1 и P2 такие, что ни одна вершина, через которую проходит P1, не лежит на пути P2 (то есть множества вершин не пересекаются), а сумма l(P1)+l(P2) минимальна.