Αντιγραφή πίνακα σε γράφο

[TSMGeorge]

Κλασικό πρόβλημα "Shortest Path".

 

Μπορούμε να βρούμε την συντομότερη διαδρομή μέσω αλγορίθμων όπως Dijkstra/BF κλπ.

 

Το θέμα είναι: πως αντιγράφω έναν πίνακα σε τέτοια μορφή ώστε να σχηματίσω τον γράφο?

 

Έστω πίνακας

 

2 1 3
4 1 7
7 2 1

Από (0,0) θέλω να πάω (2,2)

 

Τα δεδομένα για τον γράφο πως βγαίνουν από τον παραπάνω πίνακα;

 

Δομή δεδομένων για γράφο 

 

Χ1 Χ2 W1 

x1 = node 1
x2 = node 2 (χ1--->χ2) 
w1 = weight της σύνδεσης αυτής.

[imitheos]

Χωρίς να θέλω να σε προσβάλλω, γιατί δεν παίρνεις ένα βιβλίο αλγορίθμων όπως σου προτάθηκε και στα άλλα νήματα ?

 

Εκτός από αυτό/ά που σου πρότειναν, στο amazon θα βρεις εκατοντάδες βιβλία με υλοποιήσεις των αλγορίθμων σε όποια γλώσσα θέλεις και για όλα τα επίπεδα από "παιδικό" επίπεδο όπως οι σειρές της O'Reilly μέχρι το πιο ανεπτυγμένο επίπεδο.

[TSMGeorge]

Χωρίς να θέλω να σε προσβάλλω, γιατί δεν παίρνεις ένα βιβλίο αλγορίθμων όπως σου προτάθηκε και στα άλλα νήματα ?

 

Εκτός από αυτό/ά που σου πρότειναν, στο amazon θα βρεις εκατοντάδες βιβλία με υλοποιήσεις των αλγορίθμων σε όποια γλώσσα θέλεις και για όλα τα επίπεδα από "παιδικό" επίπεδο όπως οι σειρές της O'Reilly μέχρι το πιο ανεπτυγμένο επίπεδο.

 

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

Επεξ/σία 25 Οκτωβρίου 2014 από TSMGeorge

[Kercyn]

 

 

Σιγά μην κάτσω τώρα ώρες/μέρες/βδομάδες/μήνες και διαβάζω...

 

 

 

 

 

Μάλλον λάθος κλάδο έχεις επιλέξει ν' ασχοληθείς. Κανείς δεν πάει μπροστά σ' αυτόν τον τομέα χωρίς άπειρο συνεχές διάβασμα.

[defacer]

Τουλάχιστον είναι ειλικρινής.

 

Anyway for the record: σιγά μη κάτσω ούτε ένα δευτερόλεπτο επιπλέον να βοηθήσω.

[Dr.Fuzzy]

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

Επεξ/σία 27 Οκτωβρίου 2014 από Dr.Fuzzy

[gon1332]

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

[albNik]

Πάντως ο παραπανω δεν ξερω αν τα data τα εβαλε τυχαια, αλλα δεν ειναι πινάκας γειτνιασεως.

[gon1332]

Έχεις δίκαιο. Δεν είναι πίνακας γειτνιάσεως.

[TSMGeorge]

Αυτό είναι το θέμα.

 

Ότι τα δεδομένα μου είναι ένας πίνακας που ΟΛΑ τα κελιά έχουν κάποιο βάρος-κόστος.

 

Ότι παραδείγματα έχω δει με "Αναπαράσταση γράφου με-σε πίνακα" , ο πίνακας είναι τέρμα αραιός και στην διαγώνιο δεν έχει στοιχεία.

 

Εμένα ο πίνακάς μου έχει παντού στοιχεία. Δεν έχω ιδέα πως μπορώ να το κάνω σε δεδομένα για γράφο.

 

Φανταστείτε ότι το (0,0) έχει πρόσβαση στο (0,1) κ (1, 0)... το (3,3) έχει πρόσβαση στο 2,3 3,4 4,3

 

ΥΓ: Έχω δει βιβλία αλλά όλα τα παραδείγματα έχουν να κάνουν με <τα_παραπάνω_που_έγραψα>.

 

Βρήκα κάτι σε ένα βιβλίο (Εφαρμοσμένος Μαθηματικός Προγραμματισμός) ΑΛΛΑ πρέπει να ξεσκιστώ να καταλάβω και να βγάλω τον αλγόριθμο. 

[albNik]

Ο πινακας σου εχει 9 κομβους

2 1 3
4 1 7
7 2 1

 

αρα θες εναν 9x9 πινακα

καθε κομβος εχει γειτονα μονο τους διπλανους του

 

a₁₁=0 a₁₂=2+1 a₁₃=0, a₁₄=2+4 , a₁₅=0,...

....

.... a₉₉=0

[TSMGeorge]

καλή ιδέα!

 

και για 1000 στοιχεία; 1kk κόμβους (ε καλά... λίγοι είναι)

[albNik]

καλή ιδέα!

 

και για 1000 στοιχεία; 1kk κόμβους (ε καλά... λίγοι είναι)

Δεν ειναι απαραίτητο ομως. 

Μπορεις να δουλεψεις στον αρχικο πινακα