Суть задачи в том что есть N вершин.Пользователь отмечает пару из них(в зависимости от поставленной ему задачи) и программа должна построить граф но удовлетворяющий следующим условиям:
1.Указанные вершины должны обязательно соединяться ребрами
2.Сумма весов всех ребер не должна превышать указанную;
3.Длина ребра это сколько то метров.Каждый метр стоит какую то сумму.Общая цена не должна превышать указанную.

С помощью какого алгоритма это можно реализовать?Хотя бы как работать с контрольными вершинами которые ввел пользователь то есть как построить граф учитывая что между указанными вершинами должны проходить ребра?

А почему граф? Почему нельзя эти две вершины соединить одной линией и разбить эту линию на отрезки?

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

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

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