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