Търся късата дистанция м-у стартиращ вертекс и друг такъв с Dijkstra
( действащ по формулата:
if ( vertex[current]->distance < vertex[adjecent]->distance + cost ) { vertex[adjecent]->distance = vertex[current]->distance + cost; }

Проблема възниква, когато стартиращия вертекс има два прилежащи с еднакъв 'cost' за стигане до тях - например като в първата фигура -
стартира се от вертекс 'C (2)' и се търси най-късата дистанция до 'Е (4)' 'Cost'-a и до двата прилежащи вертекса е '5' и '5' :


Когато почне пробиране за съседни вертекси на верт. C(2) и релаксиране на техните дистанции, се намират B1 и D3 и техните дистанции се
релаксват до '5' и '5' съответно - фиг 2:


След което при претърсване на пула от все още не-визитирани вертекси и кой от тях е с най-малка дистанция, логично се намира първи
B(1) тъй като е преди D(3) в масива от вертекси. В резултат на това той се маркира като следващ и 'най-късата' дистанция от C(2) до E(4) се
бива намерена като C(2)-B(1)-E(4)=(5 + 2) вместо C(2)-D(3)-E(4) = (5+1) . Фиг 3:


Чудя се, какво би могло да е решението на този проблем.

както си тръгнал - няма

най-лесно: трябва да обходиш всички възможни пътища - примерно рекурсивно, като излизаш от рекурсията при лош резултат (път >= най-добрия намерен)

в теория на графите сигурно има и по-ефективни решения за подобен проблем (с графи съм се занимавал последно преди 30+г)

ПС. да си беше написал поста на анг. щеше да е по разбираем

Да, разделянето на процеса рекурсивно на по малки Dijkastri- чки, а всяка от тях на по малки е добра идея. Но ми е мъгляво как да стане ако не знам колко на брой са прилежащите вертекси на тоя който е стартиращ. Може да са 1,2 или 902. Ще го мисля.

аз обичам рекурсията - защото обикновенно е много елегантно решение (за начинаещи е по-трудна за разбиране), но тя винаги може да се замени с обикновен алгоритъм.

Мда... и аз съм забравил почти всичко

Но като цяло идеята на търсенията е да си спестиш колкото може операции. В случая първото намерено решение не е задължително най-доброто. Ако търсиш "някакво" решение е ОК, но ако търсиш най-доброто трябва да продължиш.
Не е задължително обаче да обходиш всички възможни пътища. В примера си намерил решение, което струва 7. От там насетне всеки път, който надхвърля тая цена просто го режеш.
В случая най-краткия път до В е 5, а от В до А е 6. Общо става 11, ама ти вече имаш решение на цена 7, така че няма какво да правиш в А. Следователно не те интересува какво следва след А и автоматично може да разкараш всички маршрути минаващи през А.

Усетих се къде е грешката - спирам процеса твърде рано:


Няма значение че се избира първи C(2) (който релаксва дистанциите на D(3) и E(4) до съответно '5' и '7' .
После като се продължи процеса, се избира като текущ D(3) (другата петица, щото е най-малко м-у оставащите невизитирани 11, 7 и 5 -от горната фигура)
и той релаксва E(4) да е с дистанция '6'. Накрая Е(4) релаксва дистанцията на А(0) от '11' на '7'
Т.е. - трябва да се продължава процеса докато всички вертекси са визитирани.


Аз съм го спрял на C(2) , но сега ще го пренапиша.

има, но за (много) малко нодове.
това си е класическа NP задача, при която цената на намирането на точното решение (многократно) превишава ползата от самото решаване.
пък и това се е само теория ако ти се потъва в темата (някой ще ти плаща през това време) - [Теория графов. Алгоритмический подход. Никос Кристофидес] е относително разбираема за инженери, после [Избрани глави от Теорията на графите], [Кнут. Дискретна математика, има и един Postscript about NP-hard problems. 1976] и т.н.

математическата реализация на времето (на фортран) сигурно щеше да дойде едно чекмедже и се стигна до друго, приблизително и бързо решение (за 10К нода идеше реч).
и на мен малко ми е изфирясало от главата (същите 30+ години), но ако задачата ти е как да обходиш голямо количество нодове на приблизително най-ниска 'цена', без да се повтарят, ще изровя материалите. имам ги лента, но нямам магнетофон
реализацията вървеше на вакс, ако не е твърде натоварен (беше по времето на футболното първенство в Испания), 10К нода ги решаваше за ~3 min. 'плейн' фортран
на PDP11 вървеше по-тромаво, но решаваше. имаше доста потенциал за подобрения (разбирай - изследователска дейност по аспирантура), но никой не ме пускаше до машината, че терминалите почваха да заекват, като пусна 100 симулации и отида на Витоша. после избухна демокрацията и отпадна необходимостта от възвишени мѝсли.

на съвременен хардуер би трябвало да е секунди, стига да не се портне на нещо като питон или го

Ееее, ай ся , 30+ годин... Наистина ли в embedded света Graph -овете и графините си остават недоклатени (не важат).