Если предположить, что число различных trainID относительно невелико (например, 4 в вашем примере), тогда я предлагаю использовать подход с многоуровневым графом.
Пусть количество вершин равно N, количество ребер M и количество различных trainIDs K.
Давайте разделим наш граф на K графов. (graphA, graphB, ...)
graphA содержит только ребра, помеченные буквой A. и т. д.
Вес каждого ребра в каждом из графиков равен 0.
Теперь создайте ребра между этими графами.
Граница между графами представляет собой «прыжок»
grapha [i] соединяется с graphB [i], graphC [i], ...
Каждый из этих ребер имеет вес 1.
Теперь для каждого В графе запустите алгоритм кратчайшего пути Дейкстры из V1 в этом графе и прочитайте результаты из V2 во всех графах, примите минимальное значение.
Таким образом, минимальное количество результатов для запуска дижкстры для каждого графа будет вашим минимальным количеством прыжков.
Сложность памяти O(K*(N+M))
А сложность времени O(K*(((2^K)*N+M)*log(KV)))
(2 ^ K) * N обусловлена тем фактом, что для каждого 1 <= i <= N вершины graphA [i], graphB [i] , ... должны быть связаны друг с другом, и это дает 2 ^ K соединений для каждого i, и (2 ^ K) * N соединений в общей сложности. <br>
Для случаев, когда K относительно мало , как 4 в вашем примере, но N и M довольно большие, этот алгоритм работает как шарм. Это не подходит для ситуации, когда K велико.
Я не уверен, понятно ли это. Скажите, если вам нужно более подробное объяснение.
РЕДАКТИРОВАТЬ: 
Надеюсь, что это делает мой алгоритм более понятным.
Черные края имеют вес 0, а красные края имеют вес 1.
Используя подход со слоистыми графами, мы перевели наш специальный граф в простой взвешенный граф, поэтому мы можем просто запустить алгоритм Дейкстры на нем.
Извините за некрасивое изображение.
РЕДАКТИРОВАТЬ: Так как max K = 10 , мы хотели бы убрать 2 ^ K из нашей временной сложности. Я считаю, что это можно сделать, сделав ребра, представляющие возможные прыжки, виртуальными, вместо того, чтобы физически сохранять их в списке смежности.