Какой самый простой алгоритм/решение для кратчайшего пути с одной парой через реально взвешенный неориентированный граф?

Мне нужно найти кратчайший путь через неориентированный граф, узлы которого имеют реальные (положительные и отрицательные) веса. Эти веса подобны ресурсам, которые можно получить или потерять, войдя в узел.

Общая стоимость (сумма ресурсов) пути не очень важна, но она должна быть больше 0, а длина должна быть минимально возможной.

Для примера рассмотрим такой граф:

A-start node; D-end node

A(+10)--B( 0 )--C(-5 )
     \     |    /
       \   |  /
D(-5 )--E(-5 )--F(+10)

Кратчайший путь будет A-E-F-E-D

Алгоритм Дейкстры не справляется с этой задачей, потому что он не может работать с отрицательными значениями. Поэтому я подумал о нескольких решениях:

Первое использует алгоритм Дейкстры для вычисления длины кратчайшего пути от каждого узла до выходного узла, не учитывая веса. Это можно использовать как некую эвристику, как в A*. Я не уверен, что это решение может работать, к тому же оно очень дорогостоящее. Я также думал реализовать алгоритм Флойда-Уоршалла, но не уверен, как это сделать.

Другим решением было вычисление кратчайшего пути с помощью алгоритма Дейкстры без учета весов, и если после вычисления суммы ресурсов пути она меньше нуля, пройти через каждый узел, чтобы найти соседний узел, который может быстро увеличить сумму ресурсов, и добавить его к пути (несколько раз, если необходимо). Это решение не будет работать, если есть узел, который может быть достаточным для увеличения суммы ресурсов, но находится дальше от рассчитанного кратчайшего пути.

Например:

A- start node; E- end node
A(+10)--B(-5 )--C(+40)
      \
        D(-5 )--E(-5 )

Не могли бы вы помочь мне решить эту проблему?

EDIT: Если при расчете кратчайшего пути вы достигаете точки, где сумма ресурсов равна нулю, этот путь недействителен, так как вы не можете идти дальше, если нет больше бензина.