bild
Skolan för
elektroteknik
och datavetenskap

Labb 2

Deadline för labb 2 är 2013-03-05 kl 12:00

Läs igenom labbinstruktionerna innan ni börjar.

Tips: I speciellt C++ men även Java är det ganska praktiskt att använda iteratorer för att representera vektorer/mängder/etc. För mer detaljer se Labb 1.

Observera att API-förslagen nedan är att betraktas som pseudo-kod, ni får översätta dem till ert favoritspråk på det sätt ni tycker verkar bäst. Typen graph kan variera mellan olika API, beroende på vad för extrainformation i form av kantvikter, nodmärkningar, flöden och liknande som är relevant för problemet.

Rekommenderad tidskomplexitet innebär att du bör sikta på denna komplexitet för att klara tidskraven på Kattis-uppgifterna.

Ibland testar Kattis inte exakt det som anges att ni ska implementera. Till exempel kanske ni ombeds hitta kortaste vägen från x till y men Kattis frågar bara efter den kortaste vägens längd. I sådana fall ska ni ändå lösa den uppgift som beskrivs i labblydelsen. Att Kattis godkänner uppgiften är nödvändigt men inte tillräckligt för att uppgiften ska ge poäng.

2.1 Kortaste avstånd från ett hörn

Uppgift 2.1.1: icke-negativa vikter (1p)

Implementera Dijkstras algoritm för att hitta kortaste avståndet från ett hörn till alla andra hörn i en graf med icke-negativa kantvikter.

Du ska även kunna konstruera de stigar som svarar mot de kortaste avstånden.

Kattis kommer bara att be om kortaste avstånd, men din lösning ska även lösa konstruktionsproblemet.

Förslag till API:
distance/parent[] shortest_path(graph G, node start)

Problem-id hos Kattis: shortestpath1.

Uppgift 2.1.2: tidtabellsökning (1p)

Lägg till stöd till er Dijkstra-implementation för att klara av tidtabellsgrafer, d.v.s. grafer där man bara kan använda varje kant vid vissa specifika tidpunkter.

Det är ok om ni gör detta som en separat funktion från den vanliga Dijkstra-implementationen.

Kattis kommer bara att be om kortaste avstånd, men din lösning ska även lösa konstruktionsproblemet.

Förslag till API:
distance/parent[] shortest_path(graph G, node start)

Problem-id hos Kattis: shortestpath2.

Uppgift 2.1.3: negativa avstånd (1p)

Implementera Bellman-Fords algoritm för att hitta kortaste avståndet från ett hörn till alla andra hörn i en graf där kantvikter tillåts vara negativa.

Du ska även kunna konstruera de stigar som svarar mot de kortaste avstånden.

Kattis kommer bara att be om kortaste avstånd, men din lösning ska även lösa konstruktionsproblemet.

Förslag till API:
distance/parent[] shortest_path(graph G, node start)

Problem-id hos Kattis: shortestpath3.

2.2 Kortaste avstånd mellan alla par av hörn

Uppgift 2.2.1 (1p)

Implementera Floyd-Warshalls algoritm för att hitta kortaste avstånden mellan alla par av noder i en graf med kantvikter.

Förslag till API:
distance[][] shortest_path_all_pairs(graph G)

Problem-id hos Kattis: allpairspath.

2.3 Minimalt spännande träd

Uppgift 2.3.1 (1p)

Implementera någon algoritm för att hitta ett minimalt spännande träd i en graf, förutsatt att det finns ett sådant.

Förslag till API:
tree mst(graph G)

Rekommenderad tidskomplexitet: O( (|E|+|V|)·log(|V|) ).

Problem-id hos Kattis: minspantree.

2.4 Flöden och snitt

Uppgift 2.4.1: maximalt flöde (1p)

Implementera en algoritm som hittar ett maximalt flöde i en flödesgraf.

Förslag till API:
graph max_flow(graph G, vertex s, vertex t)

Problem-id hos Kattis: maxflow.

Tips: De av er som gått ADK har här förhoppningsvis användning av Labb 1 från denna kurs, kanske bara som inspirationskälla, kanske som nästan färdig lösning som behöver putsas till.

Uppgift 2.4.2: minimalt snitt (1p)

Du får samma sorts indata som vid ett flödesproblem, men du ska hitta en delmängd U av hörnen V där s tillhör U men t tillhör V\U och summan av kapaciteterna för kanter som går från U till V\U är minimal.

Problem-id hos Kattis: mincut.

Förslag till API:
vertex_set min_cut(graph G, vertex s, vertex t)

Uppgift 2.4.3: maximalt flöde av minimal kostnad (1p)

Problemet maximalt flöde av minimal kostnad är en generalisering av maximalt flöde, där kanterna utöver kapacitet även har en kostnad. Man vill, precis som i det ursprungliga problemet, hitta ett flöde av maximal storlek, men man vill även att den totala kostnaden för det konstruerade flödet ska vara så liten som möjligt.

Kostnaden för ett flöde genom en specifik kant är flödet genom kanten multiplicerat med kostnaden för kanten. Kostnaden för ett flöde i grafen är summman av kostnaden för flödena genom varje kant.

Skriv ett program som hittar ett maximalt flöde av minimal kostnad i en flödes/kostnadsgraf.

Kattis kommer bara att be om maximal flöde och minimal kostnad, men din lösning ska även lösa konstruktionsproblemet.

Problem-id hos Kattis: mincostmaxflow.

Förslag till API:
graph max_flow(graph G, vertex s, vertex t)

2.5 Eulerväg

Uppgift 2.5.1 (1p)

Implementera en algoritm som hittar en Eulerväg i en graf, om sådan finns.

Förslag till API:
edge_list eulerian_path(graph G)

Rekommenderad tidskomplexitet: O(|E| + |V|).

Problem-id hos Kattis: eulerianpath.

Copyright © Sidansvarig: Per Austrin <popup-13@csc.kth.se>
Uppdaterad 2013-02-18