О последовательности работ на сложных комплексах

По данным задачи построим граф (ориентированную сеть)
36004520764500
Каждой вершине присвоим двойную метку (Vi, li), где Vi – вершина, из которой путь приходит, li- длина пути до этой вершины
Если в вершину возможен неоднозначный перенос метки, то рассматриваются все варианты, лучшее решение отмечается звёздочкой (٭).
Вершина V6 – метки: V3, l11*
V2, l8,
Вершина V7 – метки: V4, l15*
V3, l13,
Вершина V5 – метки: (V6, l11)
V2, l12*,
Вершина V8 – метки: V6, l15*
V5, l12,
Вершина V12 – метки: (V10, l20)
V11, l17
V9, l21*,
367665190500
Получили путь максимальной длины:
V12→V9→V8→V6→V3→V1→V0
Р: V0→V1→V3→V6→V8→V9→V12
Длина пути: Lmax=21
Ответ:
Р: V0→V1→V3→V4→V7→Vs
Длина пути: Lmax=21