Вершины — стороны улиц, а ребра — перекрестки и развороты.

Модератор: Тема перенесена из форума "C++".

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

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


Кроме того, некорректно будет обрабатываться ситуация, когда на длинной улице можно развернуться где угодно.

На длинной улице и так нельзя развернуться где угодно.

Кстати, по опыту общения с навигаторами, ВСЕ из испробованных мной НЕ учитывают эту возможность.

OSM, и о качестве того графа я вежливо промолчу.

OSM вполне себе качественный.