Обход определенных вершин графа с условиями

У меня есть неориентированный граф, похожий на приведенный ниже, мне нужно реализовать алгоритм обхода графа. Пример:
http://i.imgur.com/15L6m.png

Идея состоит в том, что каждая вершина — это город, а каждое ребро — дорога.
Вес ребра представляет собой время, необходимое для прохождения указанного ребра.
Условия следующие:

1. Каждое ребро открыто для обхода в указанном временном окне: Time Open1, Time Open2, TimeClose1, Time Close2 — текущее время должно находиться в этих интервалах для прохождения ребра.
   
2. Только некоторые вершины должны быть посещены. Вершины должны быть посещены по крайней мере один раз в указанном временном окне для каждой из них: Time Open1, Time Open2, TimeClose1, Time Close2 - текущее время должно быть в этих интервалах, чтобы вершина была помечена как посещенная.
   
3. Начальной точкой всегда является вершина 0
   

Для моего примера у меня есть:
Вершины, которые необходимо посетить, и их временное окно (значения с -1 не учитываются):

Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1 
  5    170  450  -1   -1 

Ребра открыты в следующем временном окне (значения с -1 не учитываются):

Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1 
0-4  0    210  230  770
0-5  0    260  -1   -1 
1-2  0    160  230  770
1-5  40   770  -1   -1 
2-4  80   500  -1   -1 
3-4  60   770  -1   -1 
3-5  0    770  -1   -1 

Итак, основная идея состоит в том, чтобы начать с вершины 0 и найти кратчайший путь к вершинам 1, 4 и 5 с учетом заданного времени.
Также, если, например, вы сделали 0-1, но не можете использовать 1-5, вы можете сделать 0-1-0-1-5.

Возможное решение, с которым я сейчас работаю, таково:
Начните с 0. Найдите ближайшую вершину для отметки за кратчайший период времени (я использую модифицированный алгоритм Дейкстры). Делайте это до тех пор, пока я не отмечу все необходимые вершины.
Проблема заключается в том, что я не думаю, что нахожу все возможности, потому что, как я уже сказал, вы также можете перемещаться, как комбинация 0-1-0-1-5 и в конце концов, вы можете получить более короткий маршрут.

Чтобы сделать это более ясным, я должен найти кратчайший путь, чтобы я начал с вершины 0, закончил одной целевой вершиной, в то время как я посетил все остальные целевые вершины хотя бы один раз, соблюдая условия, наложенные на ребра и целевые вершины.
Например:
Возможное решение 0 - 4 - 3 - 5 - 1 с общим временем 60+50+60+50=220
От 0 я также могу сразу перейти к 5, но, как указано в условиях, чтобы отметить вершину 5, у меня должно быть совокупное время между 170 и 450. Также, если я иду 0-4, я не могу использовать ребро 4-2, потому что оно открывается на 80, а мое совокупное время равно 60 , Обратите внимание, что я могу использовать 0-4-3, потому что 4-3 открывается на 60, а для выполнения 0-4 требуется время, равное 60.

Прежде всего ограничения заключаются в том, что я буду использовать не более 20 вершин и не более 50 ребер.

Решение 1:
0
1 4 5 0 2 5 0 2 3 0 1 3

Что я делаю, так это обхожу граф, посещая каждую соседнюю вершину, строя что-то похожее на дерево. Я перестаю расширять ветку, когда:
1. У меня слишком много дубликатов, например, у меня есть 0 1 0 4 0 1 0, поэтому я останавливаюсь, потому что у меня есть заданное количество повторяющихся значений 0, равное 4
2 . Я нашел дорогу, содержащую все вершины, которые нужно отметить
3. Я нашел дорогу, которая занимает больше времени, чем другая полная дорога
4. Я не могу создать еще один узел, потому что ребро закрыто

Решение 2.

Применяю пример @Boris Strandjev, но у меня есть некоторые проблемы:

Я должен посетить узлы 1,4 и 5 хотя бы один раз в их интервале, посещения вне интервалов разрешены, но не отмечены. Для вершины у меня есть {(‹ id1, id2id3id4>, время)}, где id1 — это ide текущей вершины, а id2-4 представляют логические значения для 1,4,5, если были посещены в указанные интервалы, время — текущее время в пути

Step1: 
{<0, 000>, 0} I can visit - {<1, 100>, 60} - chosen first lowest val
                          - {<4, 010>, 60}
                          - {<5, 000>, 60}
Step2:
{<1, 100>, 60} - {<0, 100>, 120} 
               - {<2, 100>, 110}   - chosen 
               - {<5, 100>, 110}    
Step3:
{<2, 100>, 110} - {<1, 100>, 160} - if I choose 1 again I will have a just go into a loop 
                - {<4, 110>, 170}   
Step4:
{<4, 110>, 170} - {<0, 110>, 230}
                - {<2, 110>, 230} 
                - {<3, 110>, 220}   - chosen

Step5:
{<3, 110>, 220} - {<4, 110>, 270} - again possible loop
                - {<5, 111>, 280} 
Step6:
{<5, 111>, 280} - I stop Path: 0-1-2-4-3-5 cost 280

Изменить:

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