раздвоить вершины, свети задачу, где веса на ребрах.
в зависимости, есть ли цикл отрицательного веса, использовать Дейкстру или что-то из Белмана-Форда и подобных.