Re: Странен проблем с Dijkstra алгоритъм
има, но за (много) малко нодове.
това си е класическа NP задача, при която цената на намирането на точното решение (многократно) превишава ползата от самото решаване.
пък и това се е само теория
ако ти се потъва в темата (някой ще ти плаща през това време) - [Теория графов. Алгоритмический подход. Никос Кристофидес] е относително разбираема за инженери, после [Избрани глави от Теорията на графите], [Кнут. Дискретна математика, има и един Postscript about NP-hard problems. 1976] и т.н.
математическата реализация на времето (на фортран) сигурно щеше да дойде едно чекмедже и се стигна до друго,
приблизително и бързо решение (за 10К нода идеше реч).
и на мен малко ми е изфирясало от главата (същите 30+ години), но ако задачата ти е как да обходиш голямо количество нодове на
приблизително най-ниска 'цена', без да се повтарят, ще изровя материалите. имам ги лента, но нямам магнетофон
реализацията вървеше на вакс, ако не е твърде натоварен (беше по времето на футболното първенство в Испания), 10К нода ги решаваше за ~3 min. 'плейн' фортран
на PDP11 вървеше по-тромаво, но решаваше. имаше доста потенциал за подобрения (разбирай - изследователска дейност по аспирантура), но никой не ме пускаше до машината, че терминалите почваха да заекват, като пусна 100 симулации и отида на Витоша. после избухна демокрацията и отпадна необходимостта от възвишени мѝсли.
на съвременен хардуер би трябвало да е секунди, стига да не се портне на нещо като питон или го