10.02.2005, 17:14
|
# 12
|
|
Guest
|
Цитата:
skiproff:
Насчёт алгоритма с кучами, то, кажется, у Вас что-то неправильно реализовано:
Вы при нахождении возможности уменьшения расстояния (т.е. если "$l[$v]+$d[$v][$k]<$l[$k]). Забравываете элемент в кучу, при этом "старый" элемент остаётся. Оттого куча зря растёт и рассматривается одна и та же вершина по несколько раз (лишняя трата времени). Нужно, Имхо, делать следующим образом:
1) Если текущее значения расстояние до данной верщины бесконечность ( if $l[$v]==BIG), то уменьшаем это и запихиваем в кучу.
2) если нет, то уменьшаем значение данной вершины и продвигаем вверг в куче (если меньше предка, то делаем обмен и т.д.). При этом встаёт вопрос, где находится элемент $l[$v] в куче, который решается введением вспомогательного массива position (position[v] - индекс элемента к куче). И теперь при всех операциях нужно следить за position, но это добавляет одну операцию, что не увеличивает асимтотическую сложность.
|
попробовал что-то такое реализовать. Теперь все зацикливается и все...
|
|
|
|