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:
https://i.stack.imgur.com/4sVRf.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