Търся късата дистанция м-у стартиращ вертекс и друг такъв с Dijkstra
( действащ по формулата:
if ( vertex[current]->distance < vertex[adjecent]->distance + cost ) { vertex[adjecent]->distance = vertex[current]->distance + cost; }
Проблема възниква, когато стартиращия вертекс има два прилежащи с еднакъв 'cost' за стигане до тях - например като в първата фигура -
стартира се от вертекс 'C (2)' и се търси най-късата дистанция до 'Е (4)' 'Cost'-a и до двата прилежащи вертекса е '5' и '5' :
 | | |
| Прикачени файлове: fig1.jpg [ 31.1 KiB | Прегледано 2857 пъти ] | |
| | |
Когато почне пробиране за съседни вертекси на верт. C(2) и релаксиране на техните дистанции, се намират B1 и D3 и техните дистанции се
релаксват до '5' и '5' съответно - фиг 2:
| | |
| Прикачени файлове: fig2.jpg [ 31.72 KiB | Прегледано 2857 пъти ] | |
| | |
След което при претърсване на пула от все още не-визитирани вертекси и кой от тях е с най-малка дистанция, логично се намира първи
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:
| | |
| Прикачени файлове: fig3.jpg [ 32.72 KiB | Прегледано 2857 пъти ] | |
| | |
Чудя се, какво би могло да е решението на този проблем.
е добра идея. Но ми е мъгляво как да стане ако не знам колко на брой са прилежащите вертекси на тоя който е стартиращ. Може да са 1,2 или 902. Ще го мисля.
ако ти се потъва в темата (някой ще ти плаща през това време) - [Теория графов. Алгоритмический подход. Никос Кристофидес] е относително разбираема за инженери, после [Избрани глави от Теорията на графите], [Кнут. Дискретна математика, има и един Postscript about NP-hard problems. 1976] и т.н.
