how implement dijkstra s algorithm java
Αυτό το σεμινάριο εξηγεί πώς να εφαρμόσετε τον αλγόριθμο Dijkstra στην Java για να βρείτε τις συντομότερες διαδρομές σε ένα γράφημα ή ένα δέντρο με τη βοήθεια παραδειγμάτων:
Στο προηγούμενο σεμινάριό μας για τα γραφήματα στην Java, είδαμε ότι τα γραφήματα χρησιμοποιούνται για να βρουν τη συντομότερη διαδρομή μεταξύ των κόμβων εκτός από άλλες εφαρμογές.
Για να βρούμε τη συντομότερη διαδρομή μεταξύ δύο κόμβων ενός γραφήματος, χρησιμοποιούμε ως επί το πλείστον έναν αλγόριθμο γνωστό ως ' Ο Αλγόριθμος της Dijkstra '. Αυτός ο αλγόριθμος παραμένει ο ευρέως χρησιμοποιούμενος αλγόριθμος για την εύρεση των συντομότερων διαδρομών σε ένα γράφημα ή ένα δέντρο.
=> Ελέγξτε ΟΛΑ τα Εκπαιδευτικά Java εδώ
Τι θα μάθετε:
Ο Αλγόριθμος της Dijkstra στην Ιάβα
Δεδομένου ενός σταθμισμένου γραφήματος και μιας αρχικής (πηγής) κορυφής στο γράφημα, ο αλγόριθμος Dijkstra χρησιμοποιείται για την εύρεση της μικρότερης απόστασης από τον κόμβο πηγής προς όλους τους άλλους κόμβους στο γράφημα.
Ως αποτέλεσμα του τρέχοντος αλγορίθμου Dijkstra σε ένα γράφημα, λαμβάνουμε το μικρότερο δέντρο διαδρομής (SPT) με την κορυφή της πηγής ως root.
Στον αλγόριθμο της Dijkstra, διατηρούμε δύο σύνολα ή λίστες. Το ένα περιέχει τις κορυφές που αποτελούν μέρος του δέντρου με τη μικρότερη διαδρομή (SPT) και το άλλο περιέχει κορυφές που αξιολογούνται για να συμπεριληφθούν στο SPT. Ως εκ τούτου, για κάθε επανάληψη, βρίσκουμε μια κορυφή από τη δεύτερη λίστα που έχει τη μικρότερη διαδρομή.
Ο ψευδοκώδικας για τον μικρότερο αλγόριθμο της Dijkstra δίνεται παρακάτω.
πώς να ανοίξετε το αρχείο .dat σε mac
Ψευδοκώδικας
Δίνεται παρακάτω ο ψευδοκώδικας για αυτόν τον αλγόριθμο.
procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path(V) <- infinite previous(V) <- NULL If V != S, add V to Priority Queue PQueue path (S) <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path (U) + edge_weight(U, V) if tempDistance < path (V) path (V) <- tempDistance previous(V) <- U return path(), previous() end Ας πάρουμε τώρα ένα δείγμα γραφήματος και να δείξουμε τον μικρότερο αλγόριθμο της Dijkstra .
Αρχικά, το σετ SPT (Shortest Path Tree) έχει οριστεί στο άπειρο.
Ας ξεκινήσουμε με την κορυφή 0. Οπότε για πρώτη φορά βάζουμε την κορυφή 0 στο sptSet.
sptSet = {0, INF, INF, INF, INF, INF}.
Στη συνέχεια με την κορυφή 0 στο sptSet, θα εξερευνήσουμε τους γείτονές της. Οι κορυφές 1 και 2 είναι δύο γειτονικοί κόμβοι του 0 με απόσταση 2 και 1 αντίστοιχα.
Στο παραπάνω σχήμα, έχουμε επίσης ενημερώσει κάθε γειτονική κορυφή (1 και 2) με την αντίστοιχη απόσταση από την κορυφή πηγής 0. Τώρα βλέπουμε ότι η κορυφή 2 έχει μια ελάχιστη απόσταση. Στη συνέχεια, προσθέτουμε την κορυφή 2 στο sptSet. Επίσης, διερευνούμε τους γείτονες της κορυφής 2.
Τώρα ψάχνουμε για την κορυφή με ελάχιστη απόσταση και εκείνες που δεν υπάρχουν στο spt. Διαλέγουμε την κορυφή 1 με απόσταση 2.
Όπως βλέπουμε στο παραπάνω σχήμα, από όλους τους γειτονικούς κόμβους των 2, 0 και 1 βρίσκονται ήδη στο sptSet, ώστε να τους αγνοούμε. Από τους παρακείμενους κόμβους 5 και 3, 5 έχουν το μικρότερο κόστος. Έτσι το προσθέτουμε στο sptSet και εξερευνούμε τους παρακείμενους κόμβους του.
Στο παραπάνω σχήμα, βλέπουμε ότι εκτός από τους κόμβους 3 και 4, όλοι οι άλλοι κόμβοι βρίσκονται στο sptSet. Από τα 3 και 4, ο κόμβος 3 έχει το μικρότερο κόστος. Έτσι το βάζουμε στο sptSet.
Όπως φαίνεται παραπάνω, τώρα έχουμε μόνο μία κορυφή αριστερά, δηλαδή 4 και η απόσταση από τον ριζικό κόμβο είναι 16. Τέλος, το βάζουμε στο sptSet για να πάρουμε το τελικό sptSet = {0, 2, 1, 5, 3, 4} που μας δίνει την απόσταση κάθε κορυφής από τον κόμβο πηγής 0.
Υλοποίηση του αλγόριθμου της Dijkstra στην Ιάβα
Η υλοποίηση του μικρότερου αλγορίθμου διαδρομής Dijkstra στην Java μπορεί να επιτευχθεί με δύο τρόπους. Μπορούμε είτε να χρησιμοποιήσουμε τις ουρές προτεραιότητας και τη λίστα γειτνίασης ή μπορούμε να χρησιμοποιήσουμε τον πίνακα και τις συστοιχίες προσάρτησης.
Σε αυτήν την ενότητα, θα δούμε και τις δύο υλοποιήσεις.
Χρήση ουράς προτεραιότητας
Σε αυτήν την εφαρμογή, χρησιμοποιούμε την ουρά προτεραιότητας για να αποθηκεύσουμε τις κορυφές με τη μικρότερη απόσταση. Το γράφημα ορίζεται χρησιμοποιώντας τη λίστα γειτνίασης. Ένα δείγμα προγράμματος φαίνεται παρακάτω.
import java.util.*; class Graph_pq { int dist(); Set visited; PriorityQueue pqueue; int V; // Number of vertices List adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int(V); visited = new HashSet(); pqueue = new PriorityQueue(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i adj_list = new ArrayList(); // Initialize adjacency list for every node in the graph for (int i = 0; i Παραγωγή:
Χρησιμοποιώντας Adjacency Matrix
Σε αυτήν την προσέγγιση, χρησιμοποιούμε τη μήτρα γειτονίας για να αντιπροσωπεύσουμε το γράφημα. Για το σετ spt χρησιμοποιούμε πίνακες.
Το παρακάτω πρόγραμμα δείχνει αυτήν την εφαρμογή.
import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array(), Boolean sptSet()) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v Παραγωγή:
Συχνές Ερωτήσεις
Ε # 1) Η Dijkstra λειτουργεί για μη κατευθυνόμενα γραφήματα;
Απάντηση: Εάν το γράφημα κατευθύνεται ή δεν κατευθύνεται δεν έχει σημασία στην περίπτωση του αλγόριθμου Dijkstra. Αυτός ο αλγόριθμος αφορά μόνο τις κορυφές στο γράφημα και τα βάρη.
Ε # 2) Ποια είναι η χρονική πολυπλοκότητα του αλγορίθμου Dijkstra;
Απάντηση: Η χρονική πολυπλοκότητα του αλγόριθμου της Dijkstra είναι O (V 2). Όταν υλοποιείται με την ουρά ελάχιστης προτεραιότητας, η χρονική πολυπλοκότητα αυτού του αλγορίθμου μειώνεται στο O (V + E l o g V).
Q # 3) Είναι η Dijkstra ένας άπληστος αλγόριθμος;
Απάντηση: Ναι, η Dijkstra είναι ένας άπληστος αλγόριθμος. Παρόμοια με τον αλγόριθμο Prim για την εύρεση του ελάχιστου δέντρου (MST), αυτοί οι αλγόριθμοι ξεκινούν επίσης από μια κορυφή ρίζας και επιλέγουν πάντα την βέλτιστη κορυφή με την ελάχιστη διαδρομή.
Q # 4) Είναι το Dijkstra DFS ή BFS;
Απάντηση: Δεν είναι ούτε. Αλλά καθώς ο αλγόριθμος της Dijkstra χρησιμοποιεί μια ουρά προτεραιότητας για την εφαρμογή του, μπορεί να θεωρηθεί κοντά στο BFS.
Ε # 5) Πού χρησιμοποιείται ο αλγόριθμος Dijkstra;
Απάντηση: Χρησιμοποιείται κυρίως σε πρωτόκολλα δρομολόγησης καθώς βοηθά στην εύρεση της συντομότερης διαδρομής από έναν κόμβο σε έναν άλλο κόμβο.
συμπέρασμα
Σε αυτό το σεμινάριο, συζητήσαμε τον αλγόριθμο της Dijkstra. Χρησιμοποιούμε αυτόν τον αλγόριθμο για να βρούμε τη συντομότερη διαδρομή από τον ριζικό κόμβο προς τους άλλους κόμβους στο γράφημα ή ένα δέντρο.
Συνήθως εφαρμόζουμε τον αλγόριθμο Dijkstra χρησιμοποιώντας μια ουρά προτεραιότητας, καθώς πρέπει να βρούμε την ελάχιστη διαδρομή. Μπορούμε επίσης να εφαρμόσουμε αυτόν τον αλγόριθμο χρησιμοποιώντας τη μήτρα παρακέντησης. Έχουμε συζητήσει και αυτές τις προσεγγίσεις σε αυτό το σεμινάριο.
Ελπίζουμε να βρείτε αυτό το σεμινάριο χρήσιμο.
=> Επισκεφτείτε εδώ για να δείτε τη σειρά εκπαίδευσης Java για όλους
Συνιστώμενη ανάγνωση
- Binary Search Algorithm In Java - Εφαρμογή & παραδείγματα
- Bubble Sort In Java - Java Sorting Algorithms & Code Παραδείγματα
- Ταξινόμηση εισαγωγής σε Java - Αλγόριθμος και παραδείγματα εισαγωγής
- Επιλογή Ταξινόμησης σε Java - Αλγόριθμος & Παραδείγματα Ταξινόμησης Επιλογής
- QuickSort In Java - Αλγόριθμος, απεικόνιση και υλοποίηση
- Εκπαιδευτικό πρόγραμμα JAVA για αρχάριους: 100+ πρακτικά εκπαιδευτικά βίντεο Java
- Εκμάθηση Java Reflection με παραδείγματα
- Jagged Array In Java - Εκμάθηση με παραδείγματα
