AlgoI (09-10): reeks 17
Algoritmen I (2009-2010)
reeks 17: Kortste paden in een gewogen DAG
Opwarmertje: hoeveel verbindingen kan een DAG (directed acyclic graph) van n knopen maximaal hebben?
Gegeven:
graaf.h: klasse voor gerichte en ongerichte grafen
ggraaf.h: afgeleide klasse voor gewogen grafen (nieuwe versie)
dagtest.cpp: testcode met functie voor het genereren van random DAGs.
Implementeer in dag.h in namespace DAG volgende functie:
double kortste_afstand(const GewogenGraaf<GERICHT, double> &dag, int van, int naar);
Deze geeft de totale lengte van het kortste pad tussen knoop met nummer van en knoop met nummer naar.
Geef de grootst mogelijke double terug indien naar niet bereikbaar is vanuit van.
Tip: gebruik hiervoor numeric_limits<double>::max() gedefinieerd in <limits>.
Gooi een exceptie indien de graaf niet acyclisch blijkt te zijn, of indien van of naar ongeldige knoopnummers zijn.
Welke performantie kun je garanderen?
|
Algemeen