On 5/10/05, Ryan Leavengood <mrcode / netrox.net> wrote:
> But the shortest path between two songs may not always be the path through
> the shortest songs from each song. Example (with made up songs, but I'm
> sure this could happen with "real songs"):
>
> Greg's Shortest Path:
> ---------------------
> Hello There, 3:45
> Echo It All, 2:34
> Live It Up, 3:52
> Pour It On, 2:45
> No No No, 5:01
>
> True Shortest Path:
> ---------------------
> Hello There, 3:45
> Eat a Ton, 5:34
> No No No, 5:01

Actually, what Greg is saying is that if there's another song
connecting [E] -> [N] aside from "Eat a Ton", say maybe "Elephants are
Fun" (running time 2:46), then "Elephants are Fun" will always be
preferred over "Eat a Ton" when trying to get a short playlist. So
yes, Greg's point is correct.

So maybe you won't ever care about multiple edges per node pair unless
you care about multiple criteria. I'm loathe to reintroduce that due
to the confusion it caused last time. But like Greg said:

> 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)

This is a case in which you might have more than one edge per node
pair. However, thinking about what Alex was saying earlier, wouldn't
it be more efficient to build separate graphs -- one for each
criteria? This will cause the total number of nodes in memory to
increase (d * M instead of M, where d is the number of criteria) and a
possible increase in the number of edges in memory (in the worst case,
where there is only one edge per node pair anyways, d * N instead of
N). But still, in the worst case this is only a constant multiple (by
d) in memory usage. Weighed against that is at worse the same number
of edges and at best many fewer edges to consider per graph. So
searching for best paths could become much more efficient at minimal
cost of memory.

So, I may need to concede the point that multiple edges per node pair
*aren't* ever necessary, though conceptually they can be handy.
Despite all that, I've learned a lot from this discussion and thank
you all for all the feedback!

Jacob Fugal