# Find the best path between two strings

I don't know if CS theory is the best place for this, sorry if it's not.

I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on that I can't wrap my head around. I would appreciate any help.

I need to find the best or correct string to fit between two other strings.

Given the strings strA and strB the function should analyse a database and return a string that looks like:

strA strC strD strE strB The number of strings in between can vary in number.

I have a database in place that looks something like this:

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA


This basically says that in the final string strC can come after strB but strD cannot come after strB.

I also have a secondary database which describes which strings can come before which strings. So for example...

strA strC
strA strD
strA strB

strB strA
strB strC

strC strA


But this database states that strC can come before strB, but not strD.

I have a function which, only given the beginning string can find all the strings which would fit after it in the correct order. But I need to also include an ending string and have it find the correct path between the start and finish.

I've thought about it over and over again and I don't even know where to start with this. I hope my explanation is not too convoluted. I would greatly appreciate any ideas.

This is technically not in scope for this site, but we're friendly people here :), and your question is relatively well-formed.

It sounds like what you have is a directed graph where the strings are your vertices, and your two tables are storing the "forward edges" (a -> b) and the backward edges (a <- b). The question you're asking is whether there's a way to go from one vertex in this graph to another.

The answer is to do a graph traversal (breadth-first or depth-first) on this graph. Any basic textbook on algorithms (like this one) should help.

• Thanks for pointing me in the right direction :) I'll check out the resources you mentioned. – amba88 Jul 19 '12 at 18:34