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

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

Το εργαλείο αυτό υπολογίζει τη συντομότερη διαδρομή από έναν κόμβο σε έναν άλλο σε μη κατευθυνόμενο γράφημα με θετικά ή μηδενικά βάρη. Χρησιμοποιεί τον αλγόριθμο του 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.
• Οι κόμβοι πρέπει να υπάρχουν στη λίστα ακμών.
• Το αποτέλεσμα περιλαμβάνει απόσταση, διαδρομή και πλήθος κόμβων.

Χωρίστε τα πεδία με κόμματα ASCII και χρησιμοποιήστε τελεία στα δεκαδικά βάρη. Το A,B έχει βάρος 1· το A,B, διαβάζεται σήμερα ως 0, άρα γράφετε ρητά το βάρος. Οι κενές γραμμές αγνοούνται. Τα ονόματα διακρίνουν πεζά/κεφαλαία, αφαιρούνται μόνο εξωτερικά κενά και δεν επιτρέπονται κόμματα. Ίδια αρχή και τέλος δίνουν απόσταση 0 και αυτόν τον κόμβο ως διαδρομή. Μετρούν όλοι οι καταχωρισμένοι κόμβοι. Τα αθροίσματα κινητής υποδιαστολής μπορεί να στρογγυλοποιούνται· προσβάσιμη απόσταση εκτός πεπερασμένου εύρους δίνει αριθμητικό σφάλμα.