_>Симметричной матрицей расстояний задан полный граф, задано дерево(не знаю, нужно ли это)
_>Надо определить координаты всех вершин в трехмерном пространстве. Все расстояния должны быть максимально приближенны к исходным.

Все это сильно зависит от содержимого графа. Например, для графов с небольшой "валентностью" вершин (как это называется, в общем, когда к одной вершине присоединено весьма ограниченное количество ребер, скажем не более 3-х, 4-х), прекрасно работает стохастический метод — вершины разбрасываются случайным образом, после чего, берем случайные пары вершин и двигаем их в сторону лучшего соответствия расстоянию в матрице. Коэффициент смещения постепенно уменьшаем. Рабртает это примерно так. Вот химический скетчер http://www.antigrain.com/sketcher.zip (можкт понадобиться msvcr71.dll http://www.antigrain.com/msvcr71.zip). Рисуем некий граф в виде молекулы после чего нажимаем Ctrl-I, граф "портится". Далее нажимаем Ctrl-O — при каждом нажатии выполняется некое количество итераций по "упорядочению" графа, помему, 3000. После чего коэффициент "влияния" уменьшается.
Ctrl-U использует шаблонный beautifier, специализированный для химических структур. Он срабатывает в большинстве случаев, но не всегда.