Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Následující verze
Předchozí verze
public:pb161_fall14_hw04 [2014/11/09 12:18]
Petr Svenda vytvořeno
public:pb161_fall14_hw04 [2018/02/24 19:10] (aktuální)
Řádek 95: Řádek 95:
 ==== Poznámky ==== ==== Poznámky ====
  
-  * Metoda shortestPath by měla mít časovou složitost v O( (N+M)log(N+M) ), kde je počet vrcholů a počet hran prohledávaného grafu. K její implementaci tedy můžete použít např. Dijkstrův algoritmus s tím, že vrcholy ke zpracování spolu s informací o nejlepší cestě vedoucí do daného vrcholu budou ukládány do haldy (lze použít STL kontejner typu <code cpp>​priority_queue<​pair<​PathInfo,​ string> ></​code>​ nebo přímo haldové algoritmy //​push_heap//​ a //​pop_heap//​).+  * Metoda shortestPath by měla mít časovou složitost v O( (V+E)log(V+E) ), kde je počet vrcholů a počet hran prohledávaného grafu. K její implementaci tedy můžete použít např. Dijkstrův algoritmus s tím, že vrcholy ke zpracování spolu s informací o nejlepší cestě vedoucí do daného vrcholu budou ukládány do haldy (lze použít STL kontejner typu <code cpp>​priority_queue<​pair<​PathInfo,​ string> ></​code>​ nebo přímo haldové algoritmy //​push_heap//​ a //​pop_heap//​)
 +  * Metoda addVertex by měla mít časovou složitost v O( log(V) ), kde V je počet vrcholů grafu. 
 +  * Metoda addEdge by měla mít časovou složitost v O( log(V)+log(E) ), kde V je počet vrcholů a E počet hran grafu.
   * Třída PathCompPL je jediným potomkem třídy PathComp, kterého musíte implementovat. Vaše řešení ale bude testováno i na jiných implementacích metody //​betterThan//​. Můžete se spolehnout, že ve všech těchto implementacích se metoda //​betterThan//​ bude chovat „rozumně“ (jako lineární uspořádání takové, že při prodloužení cesty o hranu bude nová cesta horší než původní).   * Třída PathCompPL je jediným potomkem třídy PathComp, kterého musíte implementovat. Vaše řešení ale bude testováno i na jiných implementacích metody //​betterThan//​. Můžete se spolehnout, že ve všech těchto implementacích se metoda //​betterThan//​ bude chovat „rozumně“ (jako lineární uspořádání takové, že při prodloužení cesty o hranu bude nová cesta horší než původní).
   * Můžete předpokládat,​ že celkové délky i ceny všech cest se vejdou do znaménkové 32bitové celočíselné proměnné.   * Můžete předpokládat,​ že celkové délky i ceny všech cest se vejdou do znaménkové 32bitové celočíselné proměnné.
  
 **Autor:** Úlohu připravil David Klaška, v případě nejasností kontaktujte na Jirku Weisera <​374154@mail.muni.cz>​ nebo na diskuzním fóru. **Autor:** Úlohu připravil David Klaška, v případě nejasností kontaktujte na Jirku Weisera <​374154@mail.muni.cz>​ nebo na diskuzním fóru.
QR Code
QR Code public:pb161_fall14_hw04 (generated for current page)