Oversikt
Forelesningsnotat
Deler av ukens temaer er oppsummert i her.
Spenntr?r: Prim, Kruskal, Bor?vka
Kommentar til videoen:
- I analysen av Bor?vka blir for l?kken (linje 3) som initaliserer treet i ikke analysert. Den kj?rer i |V| tid, og endrer ikke kj?retidsanalysen, siden |E|*log(|V|) vokser raskere enn |V|.
- Slides har blitt oppdatert med flere kommentarer i Prims pseudokode og riktig initialisering av k?en i Kruskal
Korteste stier: Dijkstra, Bellman-Ford
Korrigering i videoen:
- Bellman-Ford eksempelet p? 21min mangler det siste steget, den korteste veien til D koster -2, ikke 1.