Oversikt
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.