βοήθεια σε γράφους

[voulaji]

Θέλω να βρω τη συντομότερη διαδρομή από το Bucharest προς την Timisoara χρησιμοποιώντας κάποιο συγκεκριμένο αλγόριθμο.

 

Είπα να το κάνω με Minimmum Spanning Trees, αλλά στη πορεία μπερδεύτηκα.

 

Υπάρχει καμιά ιδέα;

[Dr.Fuzzy]

Dijkstra, Bellman-Ford, BFS, DFS, Knapsack δοκιμασες....

[voulaji]

Ποιος νομίζεις ότι είναι ο πιο απλός αλγόριθμος;

Δεν έχω πολύ χρόνο και πρέπει να την απαντήσω άμεσα.

[ippo00]

Dijkstra και την έβγαλές πανεύκολα

[voulaji]

Λοιπόν ippo00, περίμενε να τον διαβάσω και επανέρχομαι για να μου πεις εάν είναι σωστό.

[voulaji]

Που μπορώ να βρω παραδείγματα εφαρμογής του Dijsktra;

[parsifal]

Αν εννοείς παραδείγματα κώδικα, ένα google search για dijkstra algorithm [γλώσσα που σε ενδιαφέρει] θα αποδώσει πολλά σχετικά αποτελέσματα. Π.χ. εδώ υπάρχει μία υλοποίηση σε C.

[voulaji]

Δεν ψάχνω κώδικα.

Θέλω να κατανοήσω τον αλγόριθμο, για την εύρεση ελάχιστης διαδρομής.

Any idea?

[parsifal]

Δες στο λήμμα της Wikipedia. Μεταξύ άλλων, έχει εξήγηση του αλγορίθμου σε φυσική γλώσσα.

[voulaji]

Ελπίζω να μην γίνομαι κουραστική, αλλά εξακολουθώ να αναζητώ εφαρμογές-παραδείγματα για να καταλάβω τον αλγόριθμο.

[Dikemou]

Αν ψάξεις στο google κατάλληλα θα βρεις πολλά animations και simulations...

 

π.χ. αυτό του οποίο το πρώτο αποτέλεσμα οδηγεί εδώ.

[parsifal]

Κατέβασε το αρχείο που δίνεται εδώ. Περιέχει μία Java εφαρμογή που περιγράφει βήμα-βήμα την εκτέλεση του αλγορίθμου σε έναν τυχαίο γράφο που μπορείς να παράγεις με την ίδια την εφαρμογή. Είναι εξαιρετική δουλειά και νομίζω ότι δύσκολα θα βρεις κάτι περισσότερο παραστατικό και τόσο interactive...