for(int v = 0; v < count; v++)
{
int distanceThroughU = minDistance + weight[u * count + v];
if(distanceThroughU < distance[v])
distance[v] = distanceThroughU;
if(distance[v] < min)
{
u = v;
min = distance[v];
}
}
Podle mne je v tom kódu chyba. Původně jsem si říkal, že je to nějaká pekelná optimalizace. Ale dává to špatné výsledky, takže se i přes pozdní hodinu přikláním spíš k tomu, že je to chyba.
u by mělo být v rámci
for cyklu neměnné, protože se používá pro přístup do pole vah (
weight[u * count + v]). Zároveň se ale mění v případě, kdy je nalezena kratší vzdálenost (
u = v).
Správně by to myslím mělo být takhle:
int nextU = u;
for(int v = 0; v < count; v++)
{
int distanceThroughU = minDistance + weight[u * count + v];
if(distanceThroughU < distance[v])
distance[v] = distanceThroughU;
if(distance[v] < min)
{
nextU = v;
min = distance[v];
}
}
u = nextU;
S touhle opravou to má mnohem větší rozptyl výsledků, někdy je to i o dost rychlejší, než s tou chybou, někdy podstatně pomalejší. Každopádně ale to naplnění vah trvá průměrně tak 5× až 10× déle, než výpočet nejkratší cesty - takže je to spíš test použitého generátoru náhodných čísle než co jiného.
Původně jsem to chtěl tedy přepsat do paralelního zpracování, a to
u mi tam pořád překáželo. Takhle už to snad půjde líp :-)