how implement dijkstra s algorithm java
Deze tutorial legt uit hoe je het Dijkstra-algoritme in Java implementeert om de kortste routes in een grafiek of een boomstructuur te vinden met behulp van voorbeelden:
In onze eerdere tutorial over Graphs in Java hebben we gezien dat grafieken worden gebruikt om het kortste pad tussen de knooppunten te vinden, afgezien van andere applicaties.
Om het kortste pad tussen twee knooppunten van een grafiek te vinden, gebruiken we meestal een algoritme dat bekend staat als ' Dijkstra's algoritme Dit algoritme blijft het meest gebruikte algoritme om de kortste routes in een grafiek of boom te vinden.
Bekijk hier ALLE Java-tutorials
Wat je leert:
Dijkstra's algoritme in Java
Gegeven een gewogen grafiek en een beginpunt (bron) in de grafiek, wordt Dijkstra's algoritme gebruikt om de kortste afstand te vinden van het bronknooppunt tot alle andere knooppunten in de grafiek.
Als resultaat van het uitvoeren van Dijkstra's algoritme op een grafiek, verkrijgen we de kortste padboom (SPT) met de bronvertex als root.
In Dijkstra's algoritme onderhouden we twee sets of lijsten. De ene bevat de hoekpunten die deel uitmaken van de shortest path tree (SPT) en de andere bevat de hoekpunten die worden geëvalueerd om in SPT te worden opgenomen. Daarom vinden we voor elke iteratie een hoekpunt uit de tweede lijst met het kortste pad.
De pseudocode voor het Dijkstra's kortste pad-algoritme wordt hieronder gegeven.
dubbel gekoppelde lijst c ++ implementatie
Pseudocode
Hieronder wordt de pseudocode voor dit algoritme gegeven.
Laten we nu een voorbeeldgrafiek nemen en het Dijkstra's kortste pad-algoritme illustreren
Aanvankelijk is de SPT-set (Shortest Path Tree) ingesteld op oneindig.
Laten we beginnen met hoekpunt 0. Om te beginnen plaatsen we het hoekpunt 0 in sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Vervolgens met hoekpunt 0 in sptSet, zullen we zijn buren verkennen. Hoekpunten 1 en 2 zijn twee aangrenzende knooppunten van 0 met respectievelijk afstand 2 en 1.
In de bovenstaande afbeelding hebben we ook elk aangrenzend hoekpunt (1 en 2) bijgewerkt met hun respectieve afstand vanaf bronknooppunt 0. Nu zien we dat hoekpunt 2 een minimale afstand heeft. Dus vervolgens voegen we hoekpunt 2 toe aan de sptSet. Ook verkennen we de buren van hoekpunt 2.
Nu zoeken we het hoekpunt met minimale afstand en degene die er niet in spt zijn. We kiezen hoekpunt 1 met afstand 2.
Zoals we in de bovenstaande afbeelding zien, bevinden van alle aangrenzende knooppunten van 2, 0 en 1 zich al in sptSet, dus we negeren ze. Van de aangrenzende knooppunten 5 en 3 hebben er 5 de minste kosten. Dus we voegen het toe aan de sptSet en verkennen de aangrenzende knooppunten.
In de bovenstaande afbeelding zien we dat behalve de knooppunten 3 en 4, alle andere knooppunten zich in sptSet bevinden. Van de 3 en 4 heeft knooppunt 3 de minste kosten. Dus we hebben het in sptSet geplaatst.
Zoals hierboven getoond, hebben we nu nog maar één hoekpunt over, namelijk 4 en de afstand tot het rootknooppunt is 16. Ten slotte plaatsen we het in sptSet om de laatste sptSet = {0, 2, 1, 5, 3, 4} te krijgen die geeft ons de afstand van elk hoekpunt tot het bronknooppunt 0.
Implementatie van Dijkstra's algoritme in Java
Implementatie van Dijkstra's kortste pad-algoritme in Java kan op twee manieren worden bereikt. We kunnen prioriteitswachtrijen en een aangrenzende lijst gebruiken of we kunnen een aangrenzende matrix en arrays gebruiken.
In deze sectie zullen we beide implementaties zien.
Een prioriteitswachtrij gebruiken
In deze implementatie gebruiken we de prioriteitswachtrij om de hoekpunten met de kortste afstand op te slaan. De grafiek wordt gedefinieerd met behulp van de aangrenzende lijst. Hieronder ziet u een voorbeeldprogramma.
Uitgang:
Adjacency Matrix gebruiken
In deze benadering gebruiken we de aangrenzende matrix om de grafiek weer te geven. Voor spt set gebruiken we arrays.
Het volgende programma laat deze implementatie zien.
Uitgang:
Veel Gestelde Vragen
V # 1) Werkt Dijkstra voor ongerichte grafieken?
Antwoord: Of de grafiek al dan niet gericht is, maakt in het geval van Dijkstra's algoritme niet uit. Dit algoritme houdt zich alleen bezig met de hoekpunten in de grafiek en de gewichten.
Vraag 2) Wat is de tijdcomplexiteit van Dijkstra's algoritme?
Antwoord: Tijdscomplexiteit van Dijkstra's algoritme is O (V 2). Wanneer geïmplementeerd met de min-prioriteit wachtrij, komt de tijdcomplexiteit van dit algoritme neer op O (V + E l o g V).
Vraag 3) Is Dijkstra een hebberig algoritme?
Antwoord: Ja, Dijkstra is een hebberig algoritme. Vergelijkbaar met het algoritme van Prim om de minimum spanning tree (MST) te vinden, starten deze algoritmen ook vanaf een root-vertex en kiezen altijd het meest optimale vertex met het minimale pad.
Q # 4) Is Dijkstra DFS of BFS?
Antwoord: Het is geen van beide. Maar aangezien het algoritme van Dijkstra een prioriteitswachtrij gebruikt voor de implementatie, kan het worden gezien als dicht bij BFS.
V # 5) Waar wordt het Dijkstra-algoritme gebruikt?
Antwoord: Het wordt meestal gebruikt in routeringsprotocollen omdat het helpt om het kortste pad van het ene knooppunt naar het andere knooppunt te vinden.
Gevolgtrekking
In deze tutorial hebben we het algoritme van Dijkstra besproken. We gebruiken dit algoritme om het kortste pad van het hoofdknooppunt naar de andere knooppunten in de grafiek of een boom te vinden.
We implementeren het algoritme van Dijkstra meestal met behulp van een prioriteitswachtrij, omdat we het minimale pad moeten vinden. We kunnen dit algoritme ook implementeren met behulp van de aangrenzende matrix. We hebben beide benaderingen in deze tutorial besproken.
We hopen dat je deze tutorial nuttig zult vinden.
Bezoek hier om de Java-trainingsserie voor iedereen te zien
Aanbevolen literatuur
- Binair zoekalgoritme in Java - implementatie en voorbeelden
- Bubbelsortering in Java - Java-sorteeralgoritmen en codevoorbeelden
- Invoegsortering in Java - Invoegsorteeralgoritme en voorbeelden
- Selectie sorteren in Java - Selectie sorteeralgoritme en voorbeelden
- QuickSort in Java - Algoritme, illustratie en implementatie
- JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials
- Zelfstudie over reflectie in Java met voorbeelden
- Jagged Array in Java - Tutorial met voorbeelden