From: Greg Millam <ruby-talk@...>
Date: 2005-05-11T04:38:10+09:00
Subject: Re: Representing Undirected Edges (advice, please)

On Wed, May 11, 2005 at 02:57:48AM +0900, Jacob Fugal wrote:
> The goal is to determine the quickest (not necessarily shortest in
> number of songs, but shortest in running time) song chain to get from
> a starting letter to another letter B. This is a simple matter of
> finding the cheapest path in our graph between the nodes [starting
> letter] => [ending letter]. Djikstra's algorithm could be useful here,
> except (as you say):
> 
> > In the original version of Dijsktra's algorithm, there is only one  connection
> > from each edge to each other.

As far as we are concerned, there's only one effective connection from
each edge to the other: the shortest song. You will never go back to
that node, you will never need to traverse a second song from that node
to another particular node. And in no instance will a costlier
connection ever be considered over a cheaper connection connecting the
two same nodes.

As you build the map, use connections, and replace them if the new song
is shorter than the old song.

The only instances in which we need to store more than the shortest song
between two points is if we want other things, and not the shortest
directed path.

i.e: country, jazz, or blues songs have priority over others.

     we want the longest possible playlist without repeates.

     We want a play list that can approach a given time as close as
       possible. (i.e: a playlist exactly 15 minutes)

- Greg