Блог

У меня есть направленный график. Каждое ребро имеет длину и цену за его прохождение. Мне нужно найти путь с наименьшей стоимостью, который короче N. Например, график:

 1 -gt; 2 {length=12, cost=8}  1 -gt; 2 {length=8, cost=10}  2 -gt; 3 {length=21, cost=3} 2 -gt; 3 {length=12, cost=15}  3 -gt; 4 {length=18, cost=9} 3 -gt; 4 {length=12, cost=8}   

И мне нужно найти путь от 1 до 3, то есть не длиннее 45.

Какие функции я должен использовать для решения этой проблемы?