THMMY.gr

Σε ένα γράφημα, που αποτελείται από Ν κορυφές, οι οποίες συνδέονται με ακμές με δοθέντα βάρη, θέλουμε να βρούμε μια διαδρομή που να συνδέει δύο δοθείσες κορυφές. Η διαδρομή πρέπει να μην περνά δυο φορές από την ίδια κορυφή και να έχει το μικρότερο κόστος. Το κόστος της διαδρομής ισούται με το άθροισμα των βαρών των ακμών που συνδέουν τις κορυφές που ορίζουν τη διαδρομή. Για να βρούμε μια καλή διαδρομή (όχι τη βέλτιστη) εφαρμόζουμε τον πιο κάτω αλγόριθμο. Από τις κορυφές που συνδέονται με την κορυφή εκκίνησης επιλέγουμε αυτή με την οποία το βάρος της ακμής που την συνδέει είναι το ελάχιστο. Η κορυφή αυτή ενσωματώνεται στη διαδρομή, ενώ η κορυφή εκκίνησης αφαιρείται από το γράφημα. Η διαδικασία επαναλαμβάνεται θεωρώντας ως νέα κορυφή εκκίνησης την κορυφή που έχει επιλεγεί. Ο αλγόριθμος τερματίζεται όταν, με την πιο πάνω διαδικασία, επιλεγεί η κορυφή προορισμού ή διαπιστωθεί ότι δεν υπάρχουν κορυφές για επιλογή.

Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο. Το πρόγραμμα να εκτυπώνει τη διαδρομή που βρέθηκε καθώς και το συνολικό της κόστος. Σε περίπτωση που ο αλγόριθμος δε μπόρεσε να τερματίσει τη διαδρομή να τυπώνεται σχετικό μήνυμα.

Για την καταχώρηση του γραφήματος οι κορυφές να αριθμούνται από το 0 έως το Ν-1. Στο πρόγραμμα να οριστούν οι πίνακες connection και weight, δύο διαστάσεων, τύπου Ν x Ν-1. Ο πίνακας connection να ορίζει μια γραμμή για κάθε κορυφή του γραφήματος και να καταχωρεί ως τιμές για τα στοιχεία της γραμμής τους αριθμούς των κορυφών με τις οποίες συνδέεται η κορυφή που αντιστοιχεί στην γραμμή. Ο πίνακας weight να είναι ίδιος με τον πίνακα connection με τη διαφορά ότι αντί για τους αύξοντες αριθμούς των κορυφών, στις ίδιες θέσεις, να καταχωρούνται τα βάρη των ακμών οι οποίες συνδέουν τις κορυφές με την κορυφή στην οποία ανήκει η αντίστοιχη γραμμή του πίνακα.

Παράδειγμα

(φωτο απο κατω)

Η διαδρομή από την κορυφή 0 έως την κορυφή 2 θα είναι η 0,1,3,2 με κόστος 3.

Η διαδρομή από την κορυφή 0 έως την κορυφή 4 δε θα τερματιστεί από τον αλγόριθμο.