Αναλυτής Θεωρίας Γραφημάτων

Δυνατότητες και περιορισμοί

Το εργαλείο αυτό υπολογίζει τη συντομότερη διαδρομή από έναν κόμβο σε έναν άλλο σε μη κατευθυνόμενο γράφημα με θετικά ή μηδενικά βάρη. Χρησιμοποιεί τον αλγόριθμο του Dijkstra, ο οποίος απαιτεί μη αρνητικά βάρη. Οι ακμές θεωρούνται μη κατευθυνόμενες και επιτρέπονται παράλληλες ακμές.

Παράδειγμα εργασίας

Ας υποθέσουμε ότι εισάγετε τις ακμές:

A,B,2
B,C,3
A,C,10

και ορίζετε ως κόμβο εκκίνησης τον A και ως προορισμό τον C. Το εργαλείο θα επιστρέψει απόσταση 5 και διαδρομή A → B → C, επειδή το άμεσο μονοπάτι έχει βάρος 10, ενώ μέσω του B το συνολικό βάρος είναι 2+3=5.

Περιορισμοί

• Το γράφημα περιορίζεται σε 500 διακριτούς κόμβους.
• Ο αριθμός των ακμών δεν μπορεί να υπερβαίνει τις 1000.
• Αρνητικά βάρη απορρίπτονται.
• Το εργαλείο δεν υποστηρίζει κατευθυνόμενα γραφήματα, οπτικοποίηση συντεταγμένων, κεντρικότητα, ελάχιστα δέντρα επικάλυψης ή αλγορίθμους με αρνητικά βάρη.
• Δεν απαριθμεί όλες τις συντομότερες διαδρομές αν υπάρχουν περισσότερες από μία, ούτε υπολογίζει συνδεδεμένα στοιχεία.

Συχνές ερωτήσεις

Τι σημαίνει το μήνυμα «Ο κόμβος δεν βρέθηκε»;

Αυτό σημαίνει ότι ο κόμβος εκκίνησης ή προορισμού που πληκτρολογήσατε δεν υπάρχει στη λίστα ακμών. Βεβαιωθείτε ότι τα ονόματα των κόμβων γράφονται ακριβώς όπως εμφανίζονται στις ακμές, χωρίς επιπλέον κενά.

Μπορώ να χρησιμοποιήσω αρνητικά βάρη;

Όχι. Ο αλγόριθμος του Dijkstra δεν μπορεί να χειριστεί αρνητικά βάρη, επομένως το εργαλείο απορρίπτει τέτοιες εισόδους. Μηδενικά βάρη επιτρέπονται.

Γιατί δεν βλέπω όλες τις συντομότερες διαδρομές;

Το εργαλείο επιστρέφει μόνο μία συντομότερη διαδρομή (τη διαδρομή που βρίσκει ο αλγόριθμος). Δεν απαριθμεί εναλλακτικές διαδρομές ίσου μήκους.

Έλεγχος κατανόησης

• Εισάγετε τις ακμές σε μορφή κόμβος1,κόμβος2,βάρος.
• Το βάρος είναι προαιρετικό και προεπιλέγεται σε 1.
• Οι κόμβοι πρέπει να υπάρχουν στη λίστα ακμών.
• Το αποτέλεσμα περιλαμβάνει απόσταση, διαδρομή και πλήθος κόμβων.