Diskret Optimering.

7. kursusgang, fredag den 24. september 8.15-12.00

Jeg nåede ikke afsnit 5.6 i tirsdags, men jeg sagde lidt om Dijkstras algoritme, som I nok kender i forvejen.

Forelæsning i G5-109 ved LKJ:

8.15-8.45 Repetition:

Lidt mere om sammenhængen mellem Dijkstras algoritme og Primal-Dual algoritmen i afsnit 5.4.

10.40-12.00:

Algoritmer til bestemmelse af maksimum strømning: afsnit 5.6, 6.2, 6.3.
Algoritmer til bestemmelse af korteste veje 6.5.

Opgaver:

Opgave
A. Benyt metoden fra afsnit 5.4 til at bestemme en korteste vej fra s til t i grafen vist nedenfor.
B. Vend alle orienteringer af kanter i grafen nedenfor og benyt Dijkstras algoritme til at finde en korteste vej fra t til s.
C. Sammenlign de to resultater.

Opgave i Kapitel 5: 2.
Opgave i Kapitel 6: 4.