Výroba bludiště

Pospojujte všechny vrcholy hranou. Dostáváte jeden parametr:

Pro spojení dvou vrcholů použijte funkci spoj(a, b). Vzdálenost dvou vrcholů si můžete nechat spočítat funkcí vzdalenost(a, b).

Jako dárek dostáváte funkce Array.heappush(prvek, cmp) a Array.heappop(cmp). Jsou stejné jako minule, ale místo obyčejného porovnání < můžete zadat funkci cmp(a, b), která vrací, jestli a < b. Hodí se to, protože si o každém prvku v haldě budeme chtít pamatovat ještě nějaké poznámky.

Počet vrcholů:
function pospojuj(vrcholy) {

}

Jarníkův algoritmus pro body v rovině

Máme několik zadaných bodů, mezi kterými umíme počítat vzdálenost. Použijeme haldu, která řadí dvojice bodů podle vzdálenosti, jakou mezi sebou mají. U každého vrcholu poznáme, jestli je ve stromu, protože potom vrchol.sousedi.length > 0.

  1. Libovolný vrchol označíme jako kořen stromu a do haldy přidáme hrany z něj do všech ostatních vrcholů, s příslušnou délkou.
  2. Vybereme z haldy nejkratší hranu. Pokud oba vrcholy už jsou ve stromu, vybereme nějakou jinou (zpět na bod 2).
  3. Jinak hranu doopravdy přidáme do stromu. Z druhého vrcholu (ten, který zatím ve stromu nebyl) přidáme do haldy hrany z něj do všech vrcholů, co nejsou ve stromu.
  4. Jestli halda není prázdná, opakujeme od bodu 2.

Ukázková implementace

function cmp(a, b) {
  return a.delka < b.delka;
}

function pridej(vrchol, halda) {
  for (var s of vrcholy) {
    if (s !== vrchol) {
      halda.heappush({delka: vzdalenost(vrchol, s), odkud: vrchol, kam: s}, cmp);
    }
  }
}

halda = [];
pridej(vrcholy[0], halda);
while (halda.length) {
  hrana = halda.heappop(cmp);
  if (hrana.kam.sousedi.length == 0) {
    pridej(hrana.kam, halda);
    spoj(hrana.odkud, hrana.kam);
  }
}

Hledání nejkratší cesty

V předchozím cvičení jste vyrobili strom, takže mezi každými dvěma vrcholy je jenom jediná cesta. Není potřeba hledat cestu nejkratší, stačí prostě najít cestu. Následujícímu postupu se říká procházení grafu do šířky:

  1. Zavedeme si pole vrcholů v okolí. Pro začátek do něj přidáme cíl.
  2. Vytáhneme libovolný vrchol v okolí. Podíváme se na každého jeho souseda:
    1. Pokud už je označené, odkud se do něj dostat, neděláme nic.
    2. Jinak si označíme, že se do souseda dostaneme z aktuálního vrcholu, a souseda přidáme do pole vrcholů v okolí.
  3. Pokud něco zbývá v okolí, vrátíme se na bod 2.
Potom začneme na startu a pokračujeme vždycky do vrcholu, odkud jsme předtím přišli při procházení sousedů. Pokračujeme a výsledky vkládáme do pole, až dojdeme do cíle.

function nejkratsi_cesta(start, cil) {

}
délka:

Dijkstrův algoritmus

Teď zkuste k výsledku Jarníkova algoritmu přidat třeba deset náhodných hran. Náhodný vrchol získáte jako vrcholy[Math.floor(Math.random() * vrcholy.length)], jinak nemusíte nic řešit. Díky tomu už vůbec nebude jasné, která cesta je nejkratší, a musíme použít chytřejší výpočet.

  1. Do haldy přidáme všechny sousedy cílového vrcholu, ohodnocené délkou hrany, která do nich vede.
  2. Vybereme z haldy vrchol s nejmenším ohodnocením. Pokud je ohodnocení v haldě větší než skutečné ohodnocení toho vrcholu, vybereme nějaký jiný (zpět na bod 2).
  3. Hodnocení toho vrcholu nastavíme na hodnocení vytažené z haldy.
  4. Do haldy přidáme všechny sousedy toho vrcholu, ohodnocené jako ten vrchol plus délka hrany, která do nich vede.
  5. Jestli start není ohodnocený, opakujeme od bodu 2.
Jakmile je start ohodnocený, můžeme z něj začít a projít nejkratší cestu:
  1. Vybereme souseda s nejmenším ohodnocením a uděláme krok tím směrem.
  2. Pokud jsme nedošli do cíle, opakujeme od bodu 1.

Ukázková implementace

Začneme s Jarníkovým algoritmem a uděláme dvě změny:

Abychom nejkratší cestu mohli vrátit jako výsledek, projdeme pak od cíle do startu.

V následujícím kódu jsou zvýrazněné části, které bylo potřeba změnit:

function cmp(a, b) {
  return a.delka < b.delka;
}

function pridej(vrchol, halda) {
  for (var s of vrchol.sousedi) {
    if (s.vzdalenost === undefined) {
      halda.heappush({delka: vzdalenost(vrchol, s) + vrchol.vzdalenost, odkud: vrchol, kam: s}, cmp);
    }
  }
}

halda = [];
start.vzdalenost = 0;
pridej(start, halda);
while (halda.length) {
  hrana = halda.heappop(cmp);
  if (hrana.kam.vzdalenost === undefined) {
    hrana.kam.vzdalenost = hrana.delka;
    hrana.kam.odkud = hrana.odkud;
    pridej(hrana.kam, halda);
  }
}

var vysledek = [cil];
var v = cil;
while (v !== start && vysledek.length <= vrcholy.length) {
  v = v.odkud;
  vysledek.push(v);
}
return vysledek;