Edit Question - KnowledgeHub

Title Body

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.

Tags (comma-separated) Cancel