JAVA - Найти кратчайший путь между двумя узлами в взвешенном графике (также отрицательные веса)

Question

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

Входной файл выглядит примерно так:

0 6 1.4    

7 9       

0 1 3.2   
0 2 2.4   
0 3 1.7   
1 2 -2.1  
2 4 1.6   
3 4 1.8  
4 5 1.9  
4 6 1.7  
5 6 -3.1

• первая строка представляет: первый номер - начальный узел, второй - целевой узел итретья - максимальный вес, который я мог бы потратить

• вторая строка представляет номер узла и дуги

• другие строки представляютописание дуг с их весами // Пример: от узла 0 до узла 1 вес равен 3,2.

В конце, если нет возможных путей, стоимость которых меньше 1,4(как показывает первая строка ввода) программа должна вернуть значение 0. Если это возможно, она должна вернуть 1.

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

Любое предложение приветствуется

Answer 1

Просто используйте Беллан-Форд.В любом случае вы не можете решить кратчайший путь между двумя узлами, не решив кратчайший путь из одного источника.Так что просто проверьте d [source_node]> max_weight (где d [i] - массив расстояний до узла i . Поскольку вы, вероятно, используете вспомогательную матрицу, вколокольня, вы должны повторить n-1 раз по краям графика. Как я уже говорил вам сегодня утром после нашего разговора по скайпу, я нашел решение (все еще не компилируется, извините Менез)

Answer 2

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

Say results - это объект List, возвращаемый изприложение Беллмана-Форда на графе, задающее начальный узел src, где results.get(tgt) возвращает вес кратчайшего пути между узлами src и tgt.Скажем, maxWeight - это максимальный вес, который вы хотите, чтобы вес вашего кратчайшего пути.

Вы могли бы сделать что-то вроде этого:

if(!results.contain(tgt))
    return 0;
if(results.get(tgt) <= maxWeight)
    return 1;