© 1999-2003, Flemming Koch Jensen Alle rettigheder forbeholdt
Grafer Vejledende løsninger	Opgaver

 

 

1	Betragt følgende graf:
	Ovenstående graf skal anvendes til at løse følgende fire delopgaver, der er uafhængige af hinanden:
1.1	Se bort fra vægtene - dvs. betragt grafen som værende uden de anførte vægte (det er kun i denne delopgave, der ses bort fra de anførte vægte!). Anvend Moore's algoritme til at finde korteste sti fra knuden: v, til samtlige andre knuder.
1.2	Anvend Dijkstra's algoritme til at finde korteste sti fra knuden: v, til samtlige andre knuder.
1.3	Anvend Prioritet-først søgning til at finde det minimalt udspændende træ. Du skal i din besvarelse vise køens udvikling, idet du anvender de anførte navne på kanterne.
1.4	Anvend Kruskals algoritme til at finde det minimalt udspændende træ. Du skal i din besvarelse vise køens udvikling, idet du anvender de anførte navne på kanterne.