to
AleXXXSoft
Я php не знаю, так что если что я не понял необижайтесь.
Как я понял в проге считается, что граф полный. Для карты России это будет явно не так. Поэтому предлагаю улучшение программы:
1) Граф хранить не с помощью матрицы инциденции, а с помощью двух массивов.
Пусть A,B массивы рёбер ({A[ i ],B[ i ]} - ребра i=1,|U| U-множество ориентированных дуг). Т.е. ты каждое ребро заменяешь на две дуги. Сортируешь массивы А и B по значениям массива A. (т.е. теперь {A[ i ],B[ i ]} - ребра, и A[1]<=A[2]<=...<=A[|U|]). Потом вводишь новый массив F размера |I|+1 , где F[ i ]=min{j:i<=A[j]} например с помощью цикла:
Цитата:
for (val=0;i=0;i<=|U|;i++)
if (A[i]!=val) then {
for(j=val+1;j<A[i];j++) F[j]=A[i];
val=A[i];
}
F[|I|+1]=|U|+1;
|
Трудоёмкость этих операций O(2*n*log(2*n)). Но теперь все дуги, исходящие из вершины i, это {i,B[j]} j=F[ i ],F[i+1]-1. Т.е. теперь все исходящие дуги будут определяться за O(k), где k-количество исходящих дуг k<<|U|.
2) Насчёт куч скажу немного попозже, там вроде процедуру "подъёма" нужно огранизовать.
_________________________________
Продолжение:
Блин мною была допущена ошибка в куске программы.
Цитата:
Нужно строчку
F[|I|+1]=|U|+1;
заменить на
for (j=val+1;j<|I|+1;j++) F[j]=|U|+1;
|
Насчёт алгоритма с кучами, то, кажется, у Вас что-то неправильно реализовано:
Вы при нахождении возможности уменьшения расстояния (т.е. если "$l[$v]+$d[$v][$k]<$l[$k]). Забравываете элемент в кучу, при этом "старый" элемент остаётся. Оттого куча зря растёт и рассматривается одна и та же вершина по несколько раз (лишняя трата времени). Нужно, Имхо, делать следующим образом:
1) Если текущее значения расстояние до данной верщины бесконечность ( if $l[$v]==BIG), то уменьшаем это и запихиваем в кучу.
2) если нет, то уменьшаем значение данной вершины и продвигаем вверг в куче (если меньше предка, то делаем обмен и т.д.). При этом встаёт вопрос, где находится элемент $l[$v] в куче, который решается введением вспомогательного массива position (position[v] - индекс элемента к куче). И теперь при всех операциях нужно следить за position, но это добавляет одну операцию, что не увеличивает асимтотическую сложность.