У меня есть ориентированный взвешенный граф без отрицательных циклов (но, возможно, с отрицательными весами) и начальной вершины s. Я знаю, что для каждой вершины v веса ребер вдоль кратчайшего пути из s в v строго возрастают. Мне нужно найти эффективный способ вычисления кратчайшего пути от s до каждой вершины.
Я застрял на этом. Я думаю, что мне нужно расслабить края вдоль кратчайшего пути, но не уверен, как это сделать. Надеюсь, что кто-то может помочь
Спасибо!
Рон