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

Answer 1

There are many algorithms that will do better than calculating all the possible paths. Breadth-first search is the basic starting point for the family of algorithms I have in mind, Best-first search is appropriate because you have vertex costs defined, and if you can get more information about your problem space, you may be able to use A* or Dijkstra's algorithm. (In each case, finding the paths from the set of allowed starting nodes.)

Re your edit: Your path constraint (the array of node types you need to satisfy) doesn't prevent you from working with these algorithms; quite the opposite, it helps them all work better. You just need to implement them in a way that allows the path constraint to be incorporated, limiting the vertices available at each step in the search to those that are valid given the constraint.

Answer 2

As far as I understand your question you need a shortest path in a directed graph. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm should give you an idea.

regards, Jan

Answer 3

1. Calculate all the pairs of shortest paths within each equivalence block.
2. Now build a graph which has NO inter-class edges, but whose edges between classes match the shortest path within that class, leading to the specific node of another class.

Hope this is clear.

This solution is not particularly efficient, but clearly polynomial.

Answer 4

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 5

On the revision of your question it seems you ask for one node per letter - in that case it is a simple dynamic programming solution: Calculate all the shortest paths of length 1, which satisfy the beginning of your sequence, between each pair of nodes. Then having for k all such paths for all node pairs, it is trivial to construct for k+1.

Answer 6

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.

Answer 7

Here is pseudocode with dynamic programming solution:

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

your minimum cost path is min(d[n][0..m])

you can reduce size of d table to 2 rows, but it would obfuscate the solution