THMMY.gr

   Για την εισαγωγή ενός γραφήματος με Ν κορυφές, οι οποίες αριθμούνται από το 0 έως το Ν-1, ορίζεται o πίνακας graph, δύο διαστάσεων, σε κάθε γραμμή του οποίου αντιστοιχεί και μια κορυφή του γραφήματος. Κάθε γραμμή του πίνακα έχει τόσες θέσεις όσες είναι και οι κορυφές του γραφήματος που συνδέονται με την κορυφή στην οποία αντιστοιχεί η γραμμή (βαθμός της κορυφής). Στις θέσεις αυτές καταχωρούνται οι αύξοντες αριθμοί των κορυφών που συνδέονται με την κορυφή που αντιστοιχεί στη γραμμή. Για την καταχώρηση των βαρών των ακμών που συνδέουν τις κορυφές, ορίζεται o πίνακας  weights, όμοιος με τον πίνακα graph, στον οποίο, σε κάθε γραμμή, αντιστοιχούμε επίσης μια κορυφή. Στον πίνακα αυτόν έχουν αντικατασταθεί οι αύξοντες αριθμοί των κορυφών που αναγράφονται στον πίνακα graph με τα βάρη των ακμών που τις συνδέουν με την κορυφή στην οποία αντιστοιχεί η γραμμή στην οποία βρίσκονται

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

Παραδειγμα στο ethmmy αλανια

Και η πρωτη απορια απο μενα. Εχετε καταλαβει αν η διαδρομη που πληκτρολογει ο χρηστης θα ειναι απαραιτητα της μορφης 01234, 23, 04 κλπ ( δηλαδη ο επομενος αριθμος μεγαλυτερος απο το προηγουμενο ) ή μπορει να πηγαινει απο τη κορυφη π.χ 4 στην 3 και μετα στην 2 ( ή ακομα και στην 4 ) ? Μπορει δηλαδη να υπαρχει περιπτωση οπως 1043 ?

Και οι ανουσιες εργασιες συνεχιζονται με ελλειπη δεδομενα.

και γω το ειχα απορια αυτο!!!! φανταζομαι ομως οτι εννοει 01234 αφου δεν εχει παραδειγμα οπως 1043..

Γιατί όχι?
Όποια διαδρομή γουστάρει μπορεί να βάλει ο χρήστης...

Οντως,αφου εχεις βαρος για και για διαδρομες απο κορυφη μεγαλυτερου αριθμου σε μικροτερη.Πχ η διαδρομη 4,0 εχει βαρος 7.
Βεβαια στο παραδειγμα που εχει ειναι weight(i,j)=weight(j,i) κατι που δεν αναφερει στην εκφωνηση πως πρεπει να ισχυει παντα.

E αυτο ειναι προφανες νομιζω.

ΕΙΝΑΙ ΑΠΑΡΑΙΤΗΤΟ ΣΤΟ ΜΥΝΗΜΑ ΠΟΥ ΘΑ ΒΓΑΖΕΙ ΤΟ ΠΡΟΓΡΑΜΜΑ ΜΑΣ ΝΑ ΕΜΦΑΝΙΖΕΙ ΚΑΙ ΠΟΙΑ ΑΚΡΙΒΩΣ ΕΙΝΑΙ Η ΔΙΑΔΡΟΜΗ?(ΣΤΟ ΠΡΟΓΡΑΜΜΑ ΜΟΥ ΕΜΦΑΝΙΖΩ  ΜΟΝΟ  ΣΤΗΝ ΠΕΡΙΠΤΩΣΗ ΠΟΥ ΔΕΝ ΕΙΝΑΙ ΕΦΙΚΤΗ Η ΔΙΑΔΡΟΜΗ, ΠΟΙΟΣ ΣΥΝΔΥΑΣΜΟΣ ΜΑΣ ΤΟ ΧΑΛΑΣΕ, Π.Χ. 1,2,   ΔΕΝ ΕΜΦΑΝΙΖΩ ΔΗΛΑΔΗ "Η ΔΙΑΔΡΟΜΗ  1,2,3 ΔΕΝ ΕΙΝΑΙ ΕΦΙΚΤΗ ΕΞ ΑΙΤΙΑΣ ΤΟΥ 1,2" )(ΑΥΤΟ ΤΟ ΕΚΑΝΑ ΓΙΑΤΙ 1)ΔΕΝ ΗΘΕΛΑ ΝΑ ΟΡΙΣΩ EXTRA ΠΙΝΑΚΑ ΟΠΟΥ ΚΡΑΤΑΩ ΤΗ ΔΙΑΔΡΟΜΗ
2)ΜΕ ΤΟ ΠΟΥ ΔΙΑΠΙΣΤΩΘΕΙ ΟΤΙ ΕΝΑΣ ΣΥΝΔΥΑΣΜΟΣ ΔΕΝ ΕΙΝΑΙ ΣΥΜΒΑΤΟΣ ΣΤΑΜΑΤΩ ΝΑ ΔΕΧΟΜΑΙ ΤΙΜΕΣ)

Η ΕΚΦΩΝΗΣΗ ΔΕΝ ΗΤΑΝ ΠΟΛΥ ΣΑΦΗΣ ΟΠΟΤΕ ΔΕΝ ΞΕΡΩ...ΕΙΝΑΙ ΕΝΤΑΞΕΙ Η ΛΥΣΗ ΜΟΥ?

Αυτό που εγώ δεν καταλαβαίνω είναι αν πρέπει οπωσδήποτε να ορίσουμε τους πίνακες graph και weight.. Μου φαίνονται αρκετά άχρηστοι και δύσκολοι, ειδικά να οριστούν με malloc..
Ενώ πχ ένας boolean array Ν*Ν θα ήταν κομπλέ.

Αν δεν κάνω λάθος,στην c δεν ορίζεται ο τύπος bool...

Καλη ερωτηση και με ενδιαφερει και μενα. Προσωπικα ουτε εγω το εκανα να εμφανιζει τη διαδρομη που δοθηκε, αν και ειναι ευκολο, σπαταλαει μνημη( μεταξυ μας τωρα.. μηδαμηνη). Στη τελικη κανεις μια δυναμικη δεσμευση ακομα για ενα string και χρησιμοποιεις μια συναρτηση που παιρνει εναν-εναν τους χαρακτηρες και τους μετατρεπει στον ακεραιο για να κανεις τη δουλεια σου.( ομως οπως ειπα παλι δε ξερεις το μεγεθος για να δεσμευσεις μνημη )