I have an undirected graph similar to the one below, I need to implement a graph traversing algorithm.
Example:
https://i.sstatic.net/4BVPz.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:
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.
A possible solution I'm working with now is:
Start with 0. Find the nearest vertex to mark in the shortest time period (I use a
modified Dijkstra algorithm). Do this until I have marked all the vertices needed.
The problem is that I don't think I'm finding all the possibilities, because as I said
you can also move around like the 0-1-0-1-5 combination and in the end you might end up with a shorter route.
In order to make it more clear, I have to find the shortest path so that 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.
First of all the constraints are that I will use a maximum of 20 vertices and about 50 edges at max.
Solution 1:
0
1 4 5
0 2 5 0 2 3 0 1 3
What I do is traverse the graph by visiting each neighboring vertex building something similar to a tree. I stop expanding a branch when :
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
4. I can't create another node because the edge is closed
Solution 2:
Applying @Boris Strandjev example, but I have some problems:
I have to visit nodes 1,4 and 5 at least once in their interval, visits outside the intervals are allowed but not marked. For a vertex I have {(< id1, id2id3id4>, time)}, where id1 is the ide of the current vertex, and id2-4 represent bool vals for 1,4,5 if were visited in the specified intervals, time - current time in path
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
Edit:
I ended up using a combination of the 2 solutions above. Everything seems to work fine.
I have not seen a strict restriction on the amount of vertices or edges you have in the graph, so please excuse me if my solution will not work for you. Give more strict restrictions if you need any kind of improvement.
One possible solution is to extend the definition of node. Instead of considering just the city as node in your graph, add some more attributes. Keep the edge definition implicit, generating the outgoing edges on the go, so that you spare memory.
See now:
You define a node a combination of three things:
- the city the node refers to.
- the time of the visit
- a bitmap of the visited target nodes (so that you can tell whether you have already visited the all the targets).
Now the edges are a bit more complex - they lead you from city to city, but each edge also changes the time for the neighbouring node. Also keep on updating the target node bitmap with each step.
Here is an example:
You start in <city:=0, time:=0, bitmap:= (0 - true, 1...k - false)>
If you go trough the edge 0-4 you find yourself in node <city:=4, time:=60, bitmap:= ({0,4} - true, {1...k} / {4} - false)>
Keep on moving in such way between nodes, using Dejkstra algorithm and you will find your solution (as you extend the node definition, now even round abouts will be considered). You have found your solution whenever you find yourself in node that has in its bitmap all the bits set.
The number of nodes you will use in such solution is not so easy to calculate, but for relatively limited node number and quite restricted target city number it should work (the problem is that the number of resulting nodes is exponential in respect to target cities).
EDIT
Here goes the extended example you asked for:
Imagine you have such an input (I am using your notations):
Vertex To1 Tc1 To2 Tc2
1 0 40 80 120
2 40 80 -1 -1
3 0 400 -1 -1
4 30 80 120 190
Edge To1 Tc1 Weight
1-2 0 770 50
1-4 30 70 30
1-3 0 400 30
3-4 100 200 50
2-4 0 400 20
I will represent the vertices in the following form:
<1,1100> meaning: the current vertex is 1, and the second: first and second vertex are visited already in the found path.
The distance to each vertex is going to be the minimum time it takes to get to this vertex.
As you know in the process of the Dijkstra algorithm you are considering augmenting paths (meaning the best paths you found to each vertex of the front of already-reached vertices). I will dennote each augmenting path as follows: (<1,1100>, 400) meaning that the currently best time with which you can reach vertex <1,1100> is 400.
You start the algorithm with set of augmenting paths {(<1, 1000>, 0)} and distances to all vertices infinity. Now follow the next steps.
The first vertex is reached with the best augmenting path. From it the possible edges are 1-2 and 1-3 (1-4 is not available in the 0th second. they trigger two more augmenting paths: {(<2, 1100>, 50), (<3, 1010>, 30)} the distance to <1, 1000> is changed to 0.
The next step considers the best augmenting path (<3, 1010>, 30). However neighter of the outgoing edges can be used to add augmenting path: 1-3 can not be used, because the vertex 1 can not be visited at time 60. edge 3-4 can not also be used, because of the time interval. Thus the augmenting paths are now: {(<2, 1100>, 50)}.
Next step: (<2, 1100>, 50) and new augmenting paths: {(<1, 1100>, 100), (<4, 1101>, 70)}.
Next step: (<4, 1101>, 70) but it does not add new path either: vertex 2 can not be visited at time 90 and 3-4 can not be used any more. Thus the augmenting paths are {(<1, 1100>, 100)}.
Next step: (<1, 1100>, 100) which changes augmenting paths to: {(<3, 1110>, 130)}.
Next step: (<3, 1110>, 130) which changes augmenting paths to: {(<4, 1111>, 180)}.
Next step: (<4, 1111>, 180) which is the final step - we are in a state in which all target vertices are visited. So the sum-up: you can visit all the vertices in the limitations for 180 seconds.
I hope this example will help you understand my idea. You probably will need to write all considerations on sheet of paper to make sur eI do not lie with the augmenting paths.