fork download
  1. # Initialisations la matrice de transition M est à remplir séparément
  2.  
  3. :Input "Source ",S
  4. :Input "Dest ",D
  5. :dim M(1)→N
  6. :0→m
  7. :For (I,1,N)
  8. : max(m,max(vc▸li M(I))→m
  9. :End
  10. :seq((m+1)*N,I,1,N)→Dist # Distances au sommet initial
  11. :0→Dist(S)
  12. :seq(−1,I,1,N)→Chem # Arbre des plus courts chemins
  13. :seq(1,I,1,N)→NFai # Sommet passé ou non
  14.  
  15. # Boucle principale
  16.  
  17. :For (I,1,N)
  18.  
  19. # Choix du sommet
  20.  
  21. : (m+1)*N→dmin
  22. : For (J,1,N)
  23. : If Dist(J)<dmin and NFai(J)==1
  24. : Then
  25. : Dist(J)→dmin
  26. : J→T
  27. : End
  28. : End
  29. : 0→NFai(T)
  30.  
  31. # Recherche du plus court chemin partant de T
  32.  
  33. : For (J,1,N)
  34. : If NFai(J)==1 and M(T,J)≠0 and M(T,J)+Dist(T)<Dist(J)
  35. : Then
  36. : M(T,J)+Dist(T)→Dist(J)
  37. : T→Chem(J)
  38. : End
  39. : End
  40. :Disp T # Pour afficher l’ordre des sommets choisis
  41. :End
  42.  
  43. # Affichages finaux
  44.  
  45. :{D}→Chem1
  46. :D→E
  47. :While E≠S
  48. : Chem(E)→E
  49. : E→Chem1(dimL Chem1+1)
  50. :End
  51. :Disp Chem1 # On part de la destination vers la source
  52. :Disp Dist(D)
Not running #stdin #stdout 0s 0KB
stdin
Standard input is empty
stdout
Standard output is empty