Algorithme de Dijkstra

Il me semble qu'il y a une erreur dans la correction (page 5 du document joint) :
A l'étape quatre, le sommet actif devrait être (il me semble) le sommet F. En effet, à l'étape précédente on voit qu'en passant par D, F coûte 19 mais il ne faut pas oublier qu'en passant par B, F coûte 15. Si on oublie cela, alors dans le cas où l'arrête FN coûte 1, on ne trouve pas le chemin le plus court BFN.
A l'étape 5, on se rend compte que T coûte 16 en passant par C ou 23 en passant par F puis N coûte 23 en passant pas F ou 26 en passant par D. On choisit donc le sommet T en passant par C. Ce qui nous donne le chemin BCTN. Mais si FN coûtait 1 alors en ayant choisi F à l'étape 4, on aurait vu que N coûtait 16 en passant par F et T aurait coûtait 16 en passant par C. Mais N étant le point d'arrivée, aurait eu fini. Et obtenu le chemin BFN.

B

---

F

---

C

---

T

---

D

---

N

---

15B

---

12B

---

15B/15C

---

16C

---

14C

---

15B/19D

---

16C/17D

---

26D

---

16C/23F

---

26D/38F

---

26D/23T
Donc le chemin le plus court est BCTN.
La ligne "15B/19D 16C/17D 26D" me fait choisir le point F.
Dans la correction on ne calcule jamais les distances à partir du point F.

Merci pour l'algorithme.
Il est écrit en python ?
Je ne m'y connais pas en python mais j''ai installé le logiciel sur mon ordinateur.
Je n'arrive pas à exécuter le programme.
Je l'ai copié puis collé dans IDLE puis enregistré sous le nom Dijkstra. L'extension est .py
Je vois dans le programme "d=input("Depart ")
a=input("Arrivee ")" mais quand je veux poser d=B, on me renvoit que B n'est pas défini.
Encore une fois je ne m'y connais pas du tout.

Oui effectivement B et N sont des chaînes de caractères...
J'ai appliqué l'algorithme de Dijkstra pour l'exercice bac ES 2018 métropole DijkstraExo3Q3 exercice 3 question 3. Comme précédemment dans la correction correctionPage3, un point est oublié, ici c'est le point A. J'ai appliqué l'algorithme pour vérifier. L'algorithme passe également par A. Donc il y a un souci avec la correction. Pourtant c'est une correction du site APMEP. Ca me laisse perplexe.

def dijkstra():

 P=print
 M={"D":{"B":40,"H":19,"A":28},
    "B":{"F":14},
    "H":{"B":16,"A":26,"F":32},
    "A":{"B":12,"F":25},
    }

 d=input("Depart ")
 a=input("Arrivee ")

 inf=float("inf")
 p={s:"None" for s in M}
 D={s:inf for s in M}
 D[d]=0
 f=set(M)

 while f:
  smin=min(f,key=lambda s:D[ s])
  f-={smin}
  P("choix "+smin+" "+str(D[smin])+
          " venant de "+p[smin].replace("None","nulle part"))
  for s in f:
   if s in M[smin] and D[smin]+M[smin][ s]<D[ s]:
    D[ s]=D[smin]+M[smin][ s]
    p[ s]=smin

 s=a
 pc=[ s]
 while s!=d:
  s=p[ s]
  pc=[ s]+pc

 P(D[a])
 P("-".join(pc))

>>> dijkstra()
Depart D
Arrivee F
choix D 0 venant de nulle part
choix H 19 venant de D
choix A 28 venant de D
choix B 35 venant de H
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
dijkstra()
File "<pyshell#9>", line 32, in dijkstra
s=p[ s]
KeyError: 'F'

ça plante en fin d'algorithme, je ne comprends pas le message d'erreur.

Dans le corrigé de l'apmep on applique l'algorithme de Dijkstra. Je trouve le même chemin que celui de la correction mais dans l'application de l'algorithme, on doit utiliser un point, le point A, qui n'est pas utilisé dans la correction.

Dans la correction de l'apmep, je pense que c'est une erreur d'étourderie.
Dernière colonne deuxième ligne c'est A(28) et non D(28).
Du coup dans la troisième ligne c'est 40A au lieu de 68D.