Dijkstra σε C

[mayrozjack]

Καλησπέρα σε όλους!

 

Παιδεύομαι εδω και μερικες μέρες να φτιάξω ένα πρόγραμμα που θα υλοποιεί τον αλγόριθμο του Dijkstra. Έχω προχωρήσει αρκετά, αλλα με 3 μέρες συνεχή ενασχόληση νιώθω λίγο σαν ζαλισμένο κοτόπουλο... Το πρόβλημά μου είναι ότι δεν παίρνω τα αναμενόμενα αποτελέσματα, μάλλον κάπου, κάτι μου έχει ξεφύγει αλλά τώρα δεν το βλέπω με τίποτα, και έχει να κάνει με το τμήμα του κώδικα που χειρίζεται τα πεδία προκατόχων (επισημαίνω το συγκεκριμένο τμήμα στα comments του κώδικα). Επισυνάπτω τον κώδικα και ένα testbench αρχείο για δοκιμή.

 

Ευχαριστώ εκ των προτέρων!

 

Υ.Γ.: Παρακαλώ μόνο μην αρχίσετε την κριτική για το αν είναι κακογραμμένος ο κώδικας ή αν μπορεί να γίνει optimize, ας δουλέψει πρώτα σωστά και μετά βλέπουμε και τα υπόλοιπα!

 

Εννοείται πως για οτιδήποτε δεν είναι κατανοητό απλά με ρωτάτε.

https://pithos.grnet.gr/pithos/rest/[email protected]/files/d_code.zip

[Star_Light]

Γιατι γράφεις και Υ.Γ στο μηνυμά σου σου έχει κανει κάτι συγκεκριμενο κακή εντυπωση

απο το φορουμ ?

 

ειχε γινει θέμα για αυτο πριν απο κάμποσο καιρο δεν ξερω αν επηρεαστηκες απο αυτο καλο ειναι να γινεται συζητηση παντως για οτιδηποτε πειραζει ολους εμας τους χρηστες .

Οσο για τον κωδικα γιατι δεν τον βάζεις καλυτερα σε ένα απωθετηριο?

 

http://ideone.com/

 

οριστε ενα.

 

Στο προτεινω επειδη με ένα κλικ βλέπουμε απευθειας τον κώδικα που έχεις θεμα.

[mayrozjack]

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

 

Θα το έβαζα σε pastebin αλλά χρειάζεται και ένα input αρχείο για να παίξει. Anyway, μ'αρεσε αυτό που έστειλες και είπα να το ανεβάσω και εκεί: http://ideone.com/piJqA

Επεξ/σία 19 Σεπτεμβρίου 2012 από mayrozjack

[Star_Light]

Να σε ρωτησω κατι αλλο ρε συ..... έχεις δοκιμάσει να βρεις έτοιμο κώδικα για τον αλγοριθμο?

 

Πιστευω ειναι ευκολοτερο να βρεις εναν να δεις βήμα - βήμα πως κωδικοποιεί την λύση του προβλήματος

να του προσθέσεις σχόλια αλλα και τυχον δικιές σου τροποποιήσεις.

 

Πχ http://www.dreaminco...snippet2032.htm

 

αυτος εδω δεν ξερω αν ειναι καλος αλλα ειναι ενα παραδειγμα.

 

Παντως μπραβο που έκατσες προσπάθησες και έγραψες κατι δικο σου εστω και αν έχει στην αρχη

κάποια προβληματα !

 

Τωρα σχετικά με τον κώδικα σου !

 

Στην γραμμή 187

 

> if (tmp = NULL) 

 

Μαλλον θα σου ξέφυγε ένα = για να ειναι == επειδη ο = απο μονος του ειναι εκχώρησης.

Θέτει περιεχόμενα σε μια μεταβλητή.

 

Έχεις και μια i που δεν χρησιμοποιεις μεσα στην main.

[akisk]

Γραμμή 189

>
if (tmp = NULL)

ΒΟΟΜ!!

 

Καλά τα 'λεγε ο migf1 που διάβαζα νωρίτερα στο άλλο thread

[mayrozjack]

Καταρχάς ευχαριστώ για τις απαντήσεις και να ξεκαθαρίσω ότι δεν είναι ολοκληρος ο κώδικας δικός μου, παρόλο που τον έχω διαβάσει και αλλάξει τόσες φορές που τον "νιώθω" δικό μου. Στην ουσία από το μηδέν έγραψα μόνο τις συνάρτησεις Dijkstra και Queue.

 

Τώρα σχετικά με τον κώδικα αλλαξα τον τελεστή σε == αλλά πέφτω σε infinite loop. Λέω να επιχειρήσω με debugger (GDB) να δώ που "κολλάει"... Αν βλέπετε κάτι που δεν βλέπω πείτε μου.

 

Είδα πολλούς κώδικες τρίτων αλλά αναγκάζομαι να γράψω δικό μου γιατί είναι για εργασία σε μάθημα αλγορίθμων και πρέπει να συγκρίνω τον χρόνο εκτέλεσης διάφορων υλοποιήσεων. Γι'αυτο και είπα ότι οποιοδήποτε πθανό optimization μπορεί να γίνει και αργότερα, αφου πρώτα δουλέψει αυτή η υλοποίηση.

[Star_Light]

Πρέπει να δεις σε ποιο σημείο ακριβως πέφτεις σε infinite loop.

 

Κατι μου λεει πως έχεις θέμα με τους δείκτες στον κώδικα.

 

Προσπαθεις να εισάγεις έναν νεο κμβο στην αρχη της λιστας ? Θα χρειαστεις ειδικη συνάρτηση

και για να μην ξαναγράφεις έχει ο migf1 να σου δώσει έτοιμη δικια του.

 

Το x τι ειναι εδω .....

 

>

link NEW(int v, int w, link next)
{	
link x =(link malloc ( sizeof (link) );
x->id = v;
x->weight = w;
x->next = next;
return x;
}

 

Μηπως η συνάρτηση επιστρέφει έναν δεικτη σε δομη ?

 

Oταν χρησιμοποιεις την malloc (αν και καλυτερα calloc) για να δεσμεύεις μνημη μετα πρεπει να μην ξεχνάς

να την αποδεσμεύσεις κιολας !

 

> Επισης αν θες να λαβεις υποψιν σου οταν γραφεις κωδικα σε σώματα της if ή κάποιου loop το οποιο αποτελειται απο μια και μονο εντολη μην βάζεις ας πουμε αγκύλες. Οπως και στην break που ειδα οτι έβαλες.

Ειναι πιο ευαναγνωστο χωρις αυτες

 

> Κοιτα αν ξέρεις πως παιζει ο αλγοριθμος νομιζω οτι μπορεις να το κάνεις και με σκετους πινακες.

[mayrozjack]

O x είναι δείκτης σε δομή (βλ. γραμμή 13 που γίνεται το typedef). Ερώτηση: την free() σε ποιο σημείο πρέπει να την καλέσω για να αποδεσμεύσω το χώρο της malloc? Φαντάζομαι πριν κλείσω την main().... O κώδικας μέχρι το σημείο όπου κάνει update τις λίστες (πριν μπεί στο προβληματικό κομματι δηλαδή) κάνει ακριβώς αυτο που πρέπει.

 

Εχω την εντύπωση ότι καποια συνθήκη δεν είναι σωστα ορισμένη και κάπου εκει πρεπει να μπλέκονται και οι δείκτες που είπες πριν.

[imitheos]

Υ.Γ.: Παρακαλώ μόνο μην αρχίσετε την κριτική για το αν είναι κακογραμμένος ο κώδικας ή αν μπορεί να γίνει optimize, ας δουλέψει πρώτα σωστά και μετά βλέπουμε και τα υπόλοιπα!

Εννοείται πως για οτιδήποτε δεν είναι κατανοητό απλά με ρωτάτε.

Και επειδή μου έκανε πολύ κακή εντύπωση, το έγραψα για να προλάβω τους επίδοξους... Άλλωστε ξέρω πότε ο κώδικας που γράφω είναι καλός και πότε όχι

 

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

 

 

• Αλλού έχεις σχόλια με /**/ και αλλού με //
  
• Αλλού χρησιμοποιείς malloc και αλλού C99 VLAs
  
• Έχεις άχρηστα σχόλια τύπου "θέτω τιμή -1"
  
• Τα ονόματα των μεταβλητών σου δεν βοηθάνε τον αναγνώστη (di, pi, fl, p, q, dp, m)
  
• Διάφορα άλλα
  

 

 

 

Τώρα σχετικά με τον κώδικα αλλαξα τον τελεστή σε == αλλά πέφτω σε infinite loop. Λέω να επιχειρήσω με debugger (GDB) να δώ που "κολλάει"... Αν βλέπετε κάτι που δεν βλέπω πείτε μου.

 

Είδα πολλούς κώδικες τρίτων αλλά αναγκάζομαι να γράψω δικό μου γιατί είναι για εργασία σε μάθημα αλγορίθμων και πρέπει να συγκρίνω τον χρόνο εκτέλεσης διάφορων υλοποιήσεων. Γι'αυτο και είπα ότι οποιοδήποτε πθανό optimization μπορεί να γίνει και αργότερα, αφου πρώτα δουλέψει αυτή η υλοποίηση.

 

>
/* Dijkstra's algorithm  */                                                     
void Dijkstra(int k)                                                            
{
       ....

       for (i = 1; i <= n; i++) {
               while (fl != n) {

                       for (i = 1; i <= n; i++) {
                               if (D[i] <= m && D[i] != -1 && D[i] != 9999) {
                                       m = D[i];
                                       dp = i;
                               }
                       }
               }               //while close
       }                       //for close
}                               //Dijkstra close

 

Το εσωτερικό for με το εξωτερικό θα έπρεπε να έχουν i και τα δύο ? Δεν φταίει αυτό για το infinite loop αλλά ποιος ξέρει τι άλλο τέτοιο υπάρχει. Μια και δεν είναι μεγάλη ή δύσκολη συνάρτηση, πιστεύω θα είναι πιο γρήγορο να την ξαναγράψεις από την αρχή με σωστές μεταβλητές.

[Star_Light]

εγω προτεινω καταρχην να δώσεις μικρή εισοδο στο προγραμμα πχ πες οτι έχεις ξερω γω

ενα δικτυο 4 κομβων .... που έχουν πάνω τους 4 κοστη εστω 0 , 2 , 4 , 8

 

συμφωνα με τον αλγοριθμο που ξέρεις μπορεις να πεις πως θα βγει το ελάχιστο δυνατο μονοπάτι για

την διαδρομη στο δικτυο? απο οσο θυμαμαι απο την σχολη....

 

Μετα πηγαινε στην συνάρτηση που υλοποιεί αυτο τον υπολογισμο και δες πχ ειναι σφάλμα στην λογικη?

Μεσα στα loops .... ανταποκρινονται τα βήματα που έκανες πριν κοιταξεις τον κώδικα και με βάση την θεωρια του καθηγητη σου ή του βιβλιου για τον αλγοριθμο με τα βήματα που κάνεις στον κώδικα που έχεις γραψει εσυ????? ή ξερω γω εχεις κανα θεμα με τους δεικτες και δεν καλεις σωστα την συνάρτηση ωστε

να μπορεσει να κανει την δουλεια της.