Labb 2Deadline för labb 2 är fredag 13 oktober kl. 08: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 knatvikter, nodmärkningar, flöden och liknande som är relevant för problemet.
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örnUppgift 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: 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: 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: Problem-id hos Kattis: shortestpath3. 2.2 Kortaste avstånd mellan alla par av hörnUppgift 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: Problem-id hos Kattis: allpairspath. 2.3 Minimalt spännande trädUppgift 2.3.1 (1p)Implementera någon algoritm för att hitta ett minimalt spännande träd i en graf. Förslag till API: Rekommenderad tidskomplexitet: O( (|E|+|V|)·log(|V|) ). Problem-id hos Kattis: minspantree. 2.4 Flöden och snittUppgift 2.4.1: maximalt flöde (1p)Implementera en algoritm som hittar ett maximalt flöde i en flödesgraf. Förslag till API: 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: 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: 2.5 EulervägUppgift 2.5.1 (1p)Implementera en algoritm som hittar en Eulerväg i en graf, om sådan finns. Förslag till API: Rekommenderad tidskomplexitet: O(|E| + |V|). Problem-id hos Kattis: eulerianpath. |