Некоторые проблемы, которые возникают при построении маршрутов с использованием графов:

• Отсутствие механизмов отбрасывания неприемлемых вариантов. 2 Это приводит к огромным затратам ресурсов на анализ всех возможных вариантов. 2
• Сложность определения пути в густоразветвлённой сети дорог. 4 Когда между пунктами отправления и назначения есть несколько вариантов сообщений, найти оптимальный путь бывает сложно. 4
• Сложность построения маршрутов с использованием различных видов транспорта. 2 Например, при формировании маршрута из города Курган в город Ноябрьск может быть разумным привлечение автобусного сообщения на участке Курган — Тюмень, а не поиск железнодорожного маршрута с пересадками. 2
• Необходимость выбора рационального числа вершин. 4 С одной стороны, число вершин должно быть как можно больше. 4 С другой стороны, чем больше число вершин, тем сложнее транспортная сеть и дольше потребуется определение кратчайших расстояний. 4
• Необходимость учёта ограничений. 4 При построении графа нужно учитывать, например, ограничения по состоянию улиц, одностороннее движение, ограничения на движение грузового транспорта и другие. 4
• Необходимость построения маршрутов, удовлетворяющих различным ограничениям. 5 Например, прямолинейных маршрутов, маршрутов, в которых следующее ребро определяется заданным циклическим порядком, или маршрутов, в которых часть рёбер следует пройти в заданном порядке. 5