Αλγόριθμος Dijkstra

[bugman]

Φτιάχνοντας την άσκηση  στο rosettacode.org σκέφτηκα ότι μπορεί να γίνει και στη ΓΛΩΣΣΑ.

Η άσκηση έχει ως εξής:
Υπάρχουν 6 κορυφές, a b c d e f και ορίζονται ακμές μιας κατεύθυνσης και για κάθε μια από αυτές ορίζεται και ένα κόστος (ή βάρος).

Το ζητούμενο είναι να βρούμε την διαδρομή από a στο e με το μικρότερο συνολικό κόστος (ή βάρος),
Επιμέρους ζητούμενα είναι:
1. Να δείξουμε το παρακάτω πίνακα από μια δομή που θα φτιάξουμε
2. Να δείξουμε όλα τα βάρη για κάθε κορυφή σε σχέση με το a
3. Να δείξουμε τη διαδρομή.

a->b  7
a->c  9
a->f 14
b->c 10
b->d 15
c->d 11
c->f  2
d->e  6
e->f  9

Συμπληρωματικά:
α) Για την λύση του προβλήματος θα χρειαστούμε ένα πίνακα ακεραίων δυο διαστάσεων. Ο Edges[i,k] αν έχει τιμή>0 τότε σημαίνει ότι η ακμή από τη κορυφή i στη k υπάρχει και η τιμή που δίνει είναι το βάρος.
β) Ο αλγόριθμος του Dijkstra δουλεύει ως εξής:
Υπάρχουν τρεις πίνακες, ο s[], o d[] και o p[].
Τον πίνακα s[] τον χρησιμοποιούμε για να αφαιρούμε τη κορυφή που έχει το μικρότερο βάρος, βάζοντας στη θέση της το 0. Επίσης τον χρησιμοποιούμε για να αντιστρέψουμε το μονοπάτι και να το εμφανίσουμε από το a στο e.
Τον πίνακα d[] τον χρησιμοποιούμε για να βάλουμε ένα μεγάλο αρχικό βάρος (το ίδιο σε όλα), εκτός από τη κορυφή που είναι η αφετηρία, όπου βάζουμε το 0. Τον πίνακα p[] τον θέλουμε για να βάζουμε την προηγούμενη κορυφή, ώστε να μπορούμε να βρούμε το μονοπάτι.

Ο αλγόριθμος είναι μια επανάληψη για όσο υπάρχουν στο s[] μη μηδενικοί αριθμοί (δηλαδή δεν υπάρχουν κορυφές). Εντός της επανάληψης έχουμε δυο φάσεις. Η πρώτη βρίσκει τη κορυφή με το μικρότερο βάρος βάσει αυτών των κορυφών που υπάρχουν στο s[] και τοποθετεί τον αριθμό της στο u. Αμέσως μετά την αφαιρεί από το s[] (βάζουμε ένα μηδέν). Μετά ακολουθεί η δεύτερη φάση. Σε αυτήν πρέπει να εξετάσουμε όλες τις ακμές για την κορυφή u. Αν το k είναι η εξεταζόμενη κορυφή, και το Edges[u,k] δηλώνει ότι υπάρχει ακμή τότε, αν ισχύει αυτό:

d[k] > Edges[u, k] + d[u]

αλλάζουμε το d[k] με την τιμή 

Edges[u, k] + d[u]

και καταχωρούμε στο p[k] το u  (δηλώνει ότι από το u πήγαμε στο k, και αυτό είναι το πιο σύντομο)

Μόλις τελείωσει ο αλγόριθμος o d[] περιέχει τα βάρη που σχετίζονται με την αφετηρία. Αν το βάρος μιας κορυφής είναι ίσο με το μέγιστο αριθμό σημαίνει ότι δεν υπάρχει διαδρομή από την αφετηρία σε αυτή τη κορυφή.

Εδώ να προσέξει ο αναγνώστης ότι έχουμε δυο είδη βαρών. Το βάρος που καταγράφεται στη δομή (στο Edges[]) και το οποίο δεν αλλάζει, και το βάρος που καταγράφεται στο d[], το υπολογιζόμενο βάρος για δοσμένη αφετηρία.

Καλή Ανάσταση!

ΠΡΟΓΡΑΜΜΑ Dijkstra_algorithm
ΣΤΑΘΕΡΕΣ
  max_number = 1000000
  start = 1
  end = 5
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Edges[6, 6], d[6], p[6], s[6], i, k, s_heap, u, min_s_val
  ΧΑΡΑΚΤΗΡΕΣ: vertex[6] 
ΑΡΧΗ
  vertex[1] <- 'a'
  vertex[2] <- 'b'
  vertex[3] <- 'c'
  vertex[4] <- 'd'
  vertex[5] <- 'e'
  vertex[6] <- 'f'
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    ΓΙΑ k ΑΠΟ 1 ΜΕΧΡΙ 6
      Edges[i, k] <- 0
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  Edges[1, 2] <- 7
  Edges[1, 3] <- 9
  Edges[1, 6] <- 14
  Edges[2, 3] <- 10
  Edges[2, 4] <- 15
  Edges[3, 4] <- 11
  Edges[3, 6] <- 2
  Edges[4, 5] <- 6
  Edges[5, 6] <- 9
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    d[i] <- max_number
    p[i] <- -1
    s[i] <- i
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  s_heap <- 6
  d[start] <- 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    ΓΙΑ k ΑΠΟ 1 ΜΕΧΡΙ 6
      ΑΝ Edges[i, k] <> 0 ΤΟΤΕ
        ΓΡΑΨΕ vertex[i], "->", vertex[k], " ", Edges[i, k] 
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΟΣΟ s_heap > 0 ΕΠΑΝΑΛΑΒΕ             ! ΒΡΕΣ ΤΟ ΜΙΚΡΟΤΕΡΟ ΒΑΡΟΣ
    min_s_val <- max_number
    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
      ΑΝ s[i] > 0 ΤΟΤΕ
        ΑΝ min_s_val >= d[i] ΤΟΤΕ
          min_s_val <- d[i] 
          u <- i
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    s[u] <- 0
    s_heap <- s_heap - 1
    ΓΙΑ k ΑΠΟ 1 ΜΕΧΡΙ 6
      ΑΝ Edges[u, k] <> 0 ΤΟΤΕ
        ΑΝ d[k] > Edges[u, k] + d[u] ΤΟΤΕ
          d[k] <- Edges[u, k] + d[u] 
          p[k] <- u
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ "Υπολογισμός βαρών"
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 6
    ΓΡΑΨΕ vertex[i], " ", d[i] 
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
                                                ! διαδρομή για e
  i <- end
  ΓΡΑΨΕ "Διαδρομή από ", vertex[start], " μέχρι ", vertex[end], ": "
  ΑΝ d[i] = max_number ΤΟΤΕ
    ΓΡΑΨΕ "Δεν υπάρχει"
  ΑΛΛΙΩΣ
    k <- 6
    ΟΣΟ i > 0 ΕΠΑΝΑΛΑΒΕ
      s[k] <- i
      i <- p[i] 
      k <- k - 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΙΑ k ΑΠΟ k + 1 ΜΕΧΡΙ 6
      ΓΡΑΨΕ vertex[s[k]], " "
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

[Anastasis13]

Ο αλγόριθμος που έχεις δώσει δεν βρίσκει την συντομότερη διαδρομή, βρίσκει απλά μία διαδρομή.
Η διαδρομή που βρίσκεις έχει κόστος 26, ενώ η βέλτιστη έχει κόστος 20.