Ну вот немного поправил. Работает сек. 6-8. На правильность не тестировал, на прожорливость к памяти тоже.
З.Ы. Нек. "новые", написанные Вами я не читал даже (извиняйте). Кажется, они даже не нужны.
_______________________
Добавлено:
Присоединяю немного поправленную версию.
При исполнении кот. видно, что основную часть времени отжирает генерация матрицы (24.3 против 6.43 после увеличения размера). Память отжирается на этапе генерации матрицы. Имхо это достойный задел, т.к. прога оперировака с 1500^2=2 250 000 рёбрами, а в реальной задаче дуг бедет 14 000*A, где A - среднее количество исходяцих рёбер из вершины (Имхо A<=20). {Здесь, я считаю, что будет применено, написанное мною улучшение связанное со способом хранения графа}
З.Ы. Чтобы узнать, что я поправил, достаточно воспользоваться прогами fc для dos\win и diff для unix (Ex. "fc /l <file1> <file2> >> <result>, результат сраврения будет в <result>)
З.З.Ы за правильность работы не отвечаю.
З.З.З.Ы.
Цитата:
|
Сообщение от Drakosha
Дейкстра работает O(logV(V+E))
|
Интересно, откуда такая оценка взялась. Пусть граф это чепь и возьмём крайние вершины в качестве исходных, тогда между ними один путь, он же следовательно будет и оптимальным. Длина его |U|, где U - множество дуг. Оттого сложность алгоритма (любого о нах. кратчаёшего пути) не как не меньше O(|U|) (причём тождественная функция растёт быстрее логарифма от любого полинома, в том числе и квадраного).