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

Filters

Folder:

Fulltext:

Tag:

Type:

Status:

Switch cinema mode

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.

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

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

Chapters