Switch cinema mode
Current Time 0:00
Duration 0:00
Loaded: 0%
Stream Type LIVE
Remaining Time 0:00
 
1x

 Algorithms and datastuctures I: Lexture 6 (shortst paths and minimum spaning trees)

Jan Hubička

Lecture of ADS1 broadcast using zoom.

Few issues was noticed during the class:
1) cut lemma has wrong inequality it shoule be l(W)>=l(P)
2) definition of elementary cut has wrong letters

I have corrected them in the slides.

 Share

Chapters

00:01 Recall: shortest paths in valued graphs
04:23 Relaxation algorithm
14:30 Bellman-Ford algorithm
26:07 Floyd-Warshall algorithm
44:05 Minimum spaning trees: Jarník algorithm
1:08:30 Borůvka algorithm
1:19:58 Kruskal algorithm