THMMY.gr

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

Για να βρεθεί μια τέτοια διαδρομή που να δίνει μια καλή λύση (όχι τη βέλτιστη) ακολουθείται ο εξής αλγόριθμος. Επιλέγεται μια κορυφή ως αρχική κορυφή εκκίνησης. Ως επόμενη κορυφή επιλέγεται αυτή που συνδέεται με την κορυφή εκκίνησης με το μικρότερο βάρος. Η κορυφή εκκίνησης διαγράφεται από το γράφημα και η διαδικασία επαναλαμβάνεται θέτοντας ως κορυφή εκκίνησης την επόμενη κορυφή. Η διαδικασία συνεχίζεται μέχρι να καλυφθούν όλες οι κορυφές του γραφήματος. Επειδή με την πιο πάνω διαδικασία η επιλογή της αρχικής κορυφής εκκίνησης επηρεάζει το τελικό αποτέλεσμα η διαδικασία εφαρμόζεται διαδοχικά χρησιμοποιώντας μια προς μία όλες τις κορυφές του γραφήματος ως αρχικές κορυφές εκκίνησης.

Να γραφεί το πρόγραμμα που υλοποιεί τον πιο πάνω αλγόριθμό.

 

Βοηθητικές παρατηρήσεις
     Για την καταχώρηση των βαρών των ακμών του γραφήματος να ορίσετε τον πίνακας dis τύπου ΝxΝ ο οποίος, ως τιμή για το στοιχείο dis[j], να έχει το βάρος της ακμής που συνδέει την κορυφή i με την κορυφή j.

 

τον αριθμο των κορυφών τον δίνει ο χρήστης, οπότε την μνήμη για τους πινακες την δεσμευουμε με malloc, or not?

Δε να εχει πει malloc ακομα.Οποτε μαλλον κανε το οριζοντας ως max ενα αυθαιρετο αριθμο...

ιδεα μου ειναι η ειναι ιδια με την περσινη την τριτη ?  :)

Γεια σου τζορνταν!! ;)

έχει κανείς καμιά ιδέα για το πως να κάνεις exclude τις προηγούμενες κορυφές που έχεις χρησιμοποιήσει στην παρούσα διαδρομή;