This is the problem:
I have n points (p1, p2, p3, .. pn), each of them can connect to any other with a determined cost x.
Each point belongs to one of a set of point-types (for example "A" "B" "C" "D"...).
The input of the method is the path I want to follow, for example "A-B-C-A-D-B".
The output is the shortest path connecting the points of the type I give in input so for example "p1-p4-p32-p83-p43-p12" where p1 is an A-type, p4 a B-type, p32 a C-type, p83 an A-type, p43 a D-type and p12 a B-type.
The "easy" solution consists of calculating ALL the possible paths but the computational cost is very high!
Can someone find a better algorithm?
As I said in title, I don't know if it exists!
Update:
The key point that prevents me from using Dijkstra and the other similar algorithms is that I have to link the points according to type.
As input I have an array of types and I have to link in that order.
This is an image of Kent Fredric (thanks a lot) which describes the initial situation (in red allowed links)!
A real life example:
A man wants to visit a church in the morning, go to restaurant and finally visit a museum in the afternoon.
In the map there are 6 churchs, 30 restaurants and 4 museums.
He wants that the distance church-rest-museum is the minimum possible.
