Graph traversal with vertex and edge deadlines/windows Hello the question was also posted on stackoverflow, but since this is theoretical oriented, thought I'd give it a try. I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
Example: 
http://i.imgur.com/15L6m.png

The idea is that each vertex is a city, and each edge is a road.
The weight of an edge represents the time needed to traverse the specified edge.
The conditions are: 


Each edge is open for traversal in a specified time window: Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to traverse the edge.
Only some vertices must be visited. The vertices must be visited at leas once in the specified time window for each one:  Time Open1, Time Open2, TimeClose1, Time Close2 - the current time must be in these intervals in order to mark the vertex as visited.
The starting point is always vertex 0 


For my example I have: 
Vertices that must be visited and their time window (values with -1 are not taken into consideration): 

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


Edges are open in the following time window (values with -1 are not taken into 
consideration):

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 


So the basic idea is to start with vertex 0 and find the shortest route to traverse
vertices 1, 4 and 5 taking in consideration the specified time. 
Also if for example you have done 0-1 but you can't use 1-5 you can do 0-1-0-1-5.

I start with vertex 0, end with one target vertex while I have visited all other target vertices at least once respecting the conditions imposed on the edges and target vertices. 
For example: 
A possible solution is 0 - 4 - 3 - 5 - 1 with a total time of 60+50+60+50=220 
From 0 I can also go directly to 5 but as stated in conditions in order to mark vertex 5 
I must have a cumulative time between 170 and 450. Also if I go 0-4 I can't use edge 4-2 because it opens at 80 and my cumulative time is 60. Note I can use 0-4-3 because 4-3 opens at 60 and to do 0-4 it takes a time equal to 60. 
So is there a way to solve this using dijkstra or other path finding algorithms ?

Thanks in advance for any help!

Edit 

My solution for now is something like this

         0    
  1      4      5
0 2 5  0 2 3  0 1 3 


Basically I try all possibilities. The conditions for stopping in expanding a branch are: 
1. I have too many duplicates like I have 0 1 0 4 0 1 0 - so I stop because I have a set number of duplicate 0 values which is 4
2. I find a road that contains all the vertices to mark
3. I find a road that takes longer than another complete road
It is NP-hard to decide whether your problem is soluble. That's bad news from a theoretical point of view, but in practice it is possible that a heuristic algorithm will fare quite well. Also, you're (possibly) dealing with the "promise" variant of the problem, that is, you assume that a solution exists, and want to find it.

To see that the problem is NP-hard, we reduce Hamiltonian cycle to it. All the edges are always open, and they always have unit weight. The windows for each non-zero vertex are $[1,n-1]$ and $[n+1,2n-1]$; for vertex zero they are $\{0\}$ and $\{n\}$. These constraints are satisfiable only via a Hamiltonian cycle, and the converse is also true.