Предположим здесь строгое уменьшение веса между путями.
Это означает, что при рассмотрении данного пути мы должны запомнить / учитывать не только соответствующее общее расстояние, но и значение последнего веса.
Следовательно, в данном узле, мы должны запомнить разные возможные пути, т.е. разные пары (общая дистанция, последний вес), а не только одну. Это не значит, что нужно запоминать все комбинации. Например, если у нас есть два пути (13,2) и (15,2), сохраняется только (13,2). В том же духе, если мы получим (10,3) и (10,2), нужно сохранить только (10,3).
Это проиллюстрировано на рисунке ниже, надеюсь, само объясняющее. Я предполагаю здесь направленные края.
3 4 2
A(3,3) -->C (6,2), (11,5)---->D (11,4), (13,3) ------>F (13,2)
| | | NB: (15,2) skipped
|3 |5 |3
| | 4 |
S ------->B (6,6)------------>E (10, 4)
6
На практике существующие алгоритмы поиска короткого пути должны быть адаптированы для этого. Насколько я понимаю, для этой цели можно адаптировать, например, алгоритм Флойда-Уоршалла.