Dijkstra en grafenalgoritmen samenvatting

Wat is Dijkstra's algoritme?

Een algoritme voor het vinden van de kortste paden in een gewogen graaf.

Welke gegevensstructuur gebruikt Dijkstra's algoritme?

Een prioriteitsqueue, vaak geïmplementeerd met een heap.

Waarvoor wordt Dijkstra's algoritme gebruikt?

Voor het optimaliseren van routes in netwerken, zoals navigatiesystemen.

Dijkstra's algoritme is efficiënt voor ...

... positieve gewichten. Negatieve gewichten zijn problematisch.

Wat is de tijdcomplexiteit van Dijkstra's algoritme?

Met een heap is de tijdcomplexiteit $\displaystyle O((V + E) imes ext{log}(V))$, waar $\displaystyle V$ knopen zijn.

Waar begint Dijkstra's algoritme?

Bij de startknoop, met een initiële afstand van 0.

Wat gebeurt er met bezochte knopen?

Ze worden gemarkeerd, zodat ze niet opnieuw worden geëvalueerd.

Waarmee wordt de afstand naar buren vergeleken?

De huidige kortste afstand en de nieuwe berekende afstand.

Wat is een kortste pad?

Het pad met de laagste totale gewogen waarde van knopen.

Wat zijn de stappen in Dijkstra's algoritme?

- Initialiseren - Selecteren van knoop - Bijwerken van afstanden - Herhalen tot voltooid.

Waar eindigt Dijkstra's algoritme?

Bij de doelknoop of wanneer alle knopen zijn bezocht.

Is Dijkstra's algoritme altijd de beste keuze?

Onjuist. Niet geschikt voor grafen met negatieve gewichten.

Hoe worden de afstanden bijgewerkt?

Door nieuwe waarden te berekenen en te vergelijken met bestaande afstanden.

Wat is een voorbeeld van Dijkstra's algoritme?

Een graaf met steden en wegen, waarbij elke weg een gewicht heeft.

Wat zijn de voordelen van Dijkstra's algoritme?

- Efficiënt voor dichte grafen - Eenvoudige implementatie - Geschikt voor statische netwerken.

Welk type problemen lost Dijkstra op?

Optimalisatieproblemen met korte paden in netwerken.

Wat is een graaf?

Een graaf is een wiskundige structuur bestaande uit een verzameling knopen (vertices) en verbindingen (edges) tussen deze knopen.

Wat zijn knopen in een graaf?

Knopen, ook wel vertices genoemd, zijn de punten in een graaf waarop verbindingen zijn gemaakt. Ze vertegenwoordigen entiteiten zoals steden of objecten.

Wat zijn verbindingen in een graaf?

Verbindingen, of edges, zijn de lijnen die knopen met elkaar verbinden, en kunnen gewogen of ongewogen zijn.

Wat is een ongerichte graaf?

Een ongerichte graaf is een graaf waarin de verbindingen geenrichting hebben. De relatie tussen knopen is wederzijds.

Wat is een gerichte graaf?

Een gerichte graaf is een graaf waarin de verbindingen een richting hebben. Dit betekent dat de relatie tussen knopen niet noodzakelijk wederzijds is.

Geef een voorbeeld van een ongerichte graaf.

Een sociale netwerkgraaf, waar vrienden met elkaar verbonden zijn zonder richting, bijvoorbeeld A — B — C.

Geef een voorbeeld van een gerichte graaf.

Een webpagina met hyperlinks, waar pagina A een link naar pagina B heeft, maar niet omgekeerd.

Wat is een gewogen graaf?

Een gewogen graaf is een graaf waarbij elke verbinding een gewicht (of waarde) heeft, bijvoorbeeld de afstand tussen twee steden in kilometers.

Wat is een ongewogen graaf?

Een ongewogen graaf is een graaf waarbij verbindingen geen gewichten hebben. Alle verbindingen worden als gelijkwaardig beschouwd.

Vult de lege ruimte in: Een graaf met n knopen heeft maximaal _____ verbindingen.

n(n-1)/2 voor ongerichte grafen, of n(n-1) voor gerichte grafen.

Wat zijn isolaten in een graaf?

Isolaten zijn knopen zonder verbindingen. Ze zijn niet verbonden met andere knopen in de graaf.

Wat is een cyclus in een graaf?

Een cyclus is een pad dat begint en eindigt bij dezelfde knoop, en geen andere knoop meer dan eenmaal bezoekt.

Wat betekent het als een graaf verbonden is?

Een graaf is verbonden als er een pad bestaat tussen elk paar knopen, waardoor alle knopen toegankelijk zijn.

Wat is het verschil tussen een compleet en een spaarzaam graaf?

Een compleet graaf heeft verbindingen tussen elke paar knopen, terwijl een spaarzaam graaf slechts een subset van deze verbindingen heeft.

Waarvoor worden grafen gebruikt?

Grafen worden gebruikt in netwerkanalyse, routeplanning, sociale netwerken, en meer.

Waar staan de termen 'degree' en 'in-degree' voor?

Degree is het aantal verbindingen van een knoop. In-degree is het aantal verbindingen die naar een knoop wijzen in een gerichte graaf.

Wat is een toepassing van Dijkstra's algoritme?

Routing in netwerken zoals internet en mobiele communicatie.

Waarvoor worden grafen gebruikt in sociale netwerken?

Om relaties tussen gebruikers te modelleren. - Vrienden - Berichten - Groepen

Waarbij helpt het vinden van kortste paden?

Bij navigatiesystemen voor efficiënte routeplanning.

Vul de lege plek in: Toepassing in transport: _______.

Optimalisatie van routes voor vrachtwagens.

Wat is een voorbeeld van een grafenalgoritme in biologie?

Analyseren van eiwit-interactienetwerken.

Waarbij wordt het algoritme van Prim vaak gebruikt?

Bij het ontwerp van kabelnetwerken.

Wat is het verschil tussen BFS en Dijkstra?

BFS zoekt op niveau; Dijkstra zoekt op gewicht.

Waarvoor worden grafen in de game-ontwikkeling gebruikt?

Voor AI-beweging en padfinding in games.

Waarbij helpt het algoritme van Kruskal?

Bij het minimaliseren van kosten in netwerkontwerpen.

Waarvan is een voorbeeld een applicatie van grafen?

Webpagina-verbindingen in zoekmachines.

Was Dijkstra's algoritme de eerste oplossing?

Waar, het was de eerste effectieve oplossing voor kortste paden.

Hoe helpt een graaf bij stedenplanning?

Door verbindingen tussen wegen en wijken te analyseren.

Wat is een praktische toepassing in telecommunicatie?

Netwerkoptimalisatie om storingen te minimaliseren.

Vul de lege plek in: _______ maakt gebruik van grafen in de economie.

Marktanalyse en netwerkstructuren.

Wat is een voorbeeld van grafen in de gezondheidszorg?

Patiënten-route optimalisatie in ziekenhuizen.

Wat zijn twee voordelen van grafenalgoritmen?

Efficiëntie in berekeningen - Visualisatie van complexe netwerken.