-------------------------------1115734924
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit

Dear Jacob,
 
now you have confused me almost totally.
Actually, I was first responding to the subject because I had sowhat  vaguely
in mind that it might help to formulate the problem in as a
shortest-path problem (define a cost function and try to minimise it. For  
example,
in the song problem, pay me $1000000 each time the subsequent song  doesn't 
start with the letter
the previous ended with. Otherwise, pay nothing. If you have to pay nothing  
after going through the whole path, you have found a correct solution and I  
am still poor.
 
 
For this sort of problem, there is a way to find the "single-source  shortest 
path solution"
called Dijkstra's algorithm, which is nicely described here:
 
_http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html_ 
(http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html) 
 
I feel that the way this algorithm works should tell one also how to  
implement paths
as data structures (there is (non Ruby-) code and an animation on that  
website).
 
My confusion is about your use of multiple criteria/connections/... .
In the original version of Dijsktra's algorithm, there is only one  connection
from each edge to each other.
I feel that that's also enough, somehow, because you are assigning  some
overall value to a specific path in the end, and it's only because of that  
that
you can put order into the set of all possible paths to choose the  best.
The value you assign to a specific connection may well be a result of  many
factors, but in the end, you have to come up with  a numeric value for  it.
Otherwise, they cannot be classified - going from New York to  Philadelphia
by plane may be three times as expensive as going there by car, but  only
two times as nice - so what do you do?
 
So I'd now  tend to use a vector-of-factors incidence matrix and to  evaluate
these to assign a value to measure 'how nice is it to go from A to B via  
i-j?'
 
Best regards,
 
Axel 

-------------------------------1115734924--