Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
89 views

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

in algorithms by (730 points) | 89 views

Please log in or register to answer this question.

261 questions

253 answers

274 comments

2.9k users