Мне нужно найти путь в графе, который должен удовлетворять довольно сложным правилам ... Я думаю, что эта проблема связана с "найти все пути между двумя узлами", но я не уверен в этом.
Существуют ли эффективные ключевые слова или алгоритмы для этой проблемы?
Правила таковы: граф является ориентированным графом и имеет два веса;один - расстояние, другой - стоимость.
Форма ввода выглядит следующим образом: (number_of_vertices (V), number_of_edges (E), допустимое общее расстояние (D)) и следующие E-строки выглядят следующим образом: (start_node, end_node, cost, distance)
если я заплачу x $ (стоимость), то я могу взять любые ребра дешевле, чем x $.Кроме того, я могу пройти только D миль.
индекс начальных вершин всегда равен 0
Все, что мне нужно сделать, это найти «самый дешевый» путь от начального узла до конечного узла.
ex)
5 6 4 -> (количество вершин, number_of_edges, allow_total_distance)
0 1 2 1 -> (начальный узел, конечный узел, стоимость, расстояние)
1 4 3 4
1 3 1 1
3 2 3 1
2 4 2 1
0 4 5 3
В этом случае я долженнайдите самый дешевый путь от 0 до 4.
Возможны следующие пути:
0 1 4 / стоимость: 5, расст: 5
0 1 3 2 4 / стоимость: 3, расст:4
0 4 / стоимость: 5, dist: 3
И ответ 0 1 3 2 4, потому что этот маршрут имеет самую низкую стоимость (3 $) и соответствует допустимому общему расстоянию (4 <= 4). </p>
Я попытался решить эту проблему путем нахождения всех путей между двумя узлами, вычисления длины и стоимости всех путей и их сортировки.
Я использовал этот алгоритм, чтобы найти все пути ... но требуется O (n!), Что слишком поздно ..
Есть ли эффективные ключевые слова или алгоритмы для этой проблемы?