"Dave Blandston" <gra### [at] earthlinknet> wrote in message
news:4158febb$1@news.povray.org...
> "pan" <pan### [at] syixcom> wrote in message news:4158fb48@news.povray.org...
> > minimum spanning trees (MST) can be maps of nodes and edges such that a
> > single path
> > is calculated that all nodes lie on and such that the total length of
the
> > path is
> > at (or near) a minimum value.
>
> Does the path double-back? Otherwise, it looks like there are a bunch of
> dead ends.
>
No - the algorithm is designed to prevent any loops.
That's the purpose of it.
Think of a computer network - you don't want ethernet loops in your routing.

A spanning tree is defined as a single path that connects all points in the
graph.
A minimal spanning tree optimizes that path according to what you're
after. Usually a total distance thing, but the edges could represent
financial costs, etc.

The images I posted are to minimize the total sum length of a path
that connects all points in the graph.

You put into your database all points and a table of values for each
possible
connection between all pairs of points. For 256 points you have 34,000 +
unique
possible connections. (Halved because path A -> B is likely the same value
as
path B -> A). If you drew a graph with all those lines on it you would
probably never get any use from the graph. This algorithm can be
biased and weighted to manipulate the final optimized path. Lots
easier to let the computer untangle the knots.

Post a reply to this message