What algorithm can I use to find the shortest path between specified node types in a graph?

Question

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.

Answer 1

You can use the Floyd–Warshall algorithm. Here's the pseudocode given by WikiPedia:

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

I had to write a program for an algorithms course about this same problem. This algorithm worked like a charm! Goodluck.

Answer 2

As Jan mentioned, you just need a normal boring shortest path algorithm (like Dijkstra's or Floyd's algorithm); however, you need to transform your input graph so that the output path will respect your path constraint.

Given a path constraint of: A - B - A

Create a new graph G and insert all of the vertexes from A into G with new labels like a_01. Then insert all the vertexes from B into G and connect the A vertexes with the B vertexes (edges should be directed towards the newly inserted nodes) copying the costs from the original graph. You then repeat this step with A (and any other path components) connecting the newly inserted vertexes to those in B. Thus, you create a graph where only the paths that exist satisfy the path constraint. You can then use normal shortest path algorithms.

The key insight is that when you revisit a class you are actually visiting a distinct set of nodes and that you only want edges that connect adjacent classes of nodes.