fork download
copy 
  1. import numpy as np
  2. from scipy.sparse.csgraph import dijkstra
  3. from scipy.sparse import csr_matrix
  4.  
  5. # Fonction pour créer la matrice d'adjacence du graphe
  6. def creer_represetation_matricielle():
  7.     matrice = np.zeros((9, 9))
  8.     matrice[0][1] = 680
  9.     matrice[0][2] = 360
  10.     matrice[0][3] = 300
  11.     matrice[1][4] = 90
  12.     matrice[1][5] = 100
  13.     matrice[3][1] = 160
  14.     matrice[3][6] = 720
  15.     matrice[3][7] = 220
  16.     matrice[4][3] = 190
  17.     matrice[4][5] = 110
  18.     matrice[4][6] = 210
  19.     matrice[5][6] = 120
  20.     matrice[5][8] = 400
  21.     matrice[6][8] = 130
  22.     matrice[7][6] = 630
  23.     matrice[7][8] = 550
  24.     return matrice
  25.  
  26. # Fonction pour formater les chaînes ou nombres pour l'affichage
  27. def formater(n):
  28.     return '{:10s}'.format(str(n))
  29.  
  30. # Fonction d'affichage de la matrice d'adjacence
  31. def afficher_matrice(matrice, sommets):
  32.     print("La matrice est:")
  33.     print("_____" * len(sommets))
  34.     print(formater(' '), end="")
  35.     for i in range(len(sommets)):
  36.         print(formater(sommets[i]), end="")
  37.     print()
  38.     print("_____" * len(sommets))
  39.     for i in range(len(matrice)):
  40.         print(formater(sommets[i]), end="")
  41.         for j in range(len(matrice[i])):
  42.             val = "-" if matrice[i][j] == 0 else int(matrice[i][j])
  43.             print(formater(val), end="")
  44.         print()
  45.  
  46. # Fonction qui applique l'algorithme de Dijkstra
  47. def algo_dijkstra(matrice):
  48.     graphe = csr_matrix(matrice)
  49.     distances, indices_precedents = dijkstra(graphe, return_predecessors=True, indices=0)
  50.     return distances, indices_precedents
  51.  
  52. # Affichage des distances minimales depuis le sommet source
  53. def afficher_distance_minimales(distances, indices_precedents, sommets):
  54.     print("\nLes longueurs minimales à partir de", sommets[0], "sont :")
  55.     print("_____" * len(sommets))
  56.     for i in range(len(sommets)):
  57.         print(formater(sommets[i]), end="")
  58.     print("\n" + "_____" * len(sommets))
  59.     for i in range(len(sommets)):
  60.         dist = distances[i]
  61.         indice = indices_precedents[i]
  62.         if indice >= 0:
  63.             precedent = sommets[indice]
  64.             s = formater(str(int(dist)) + ":" + precedent)
  65.             print(s, end="")
  66.         else:
  67.             print(formater("-"), end="")
  68.     print()
  69.  
  70. # Affichage du chemin minimal du sommet source à la destination
  71. def afficher_chemin_minimales(distances, indices_precedents, sommets):
  72.     print("\nLe chemin critique allant de", sommets[0], "à", sommets[-1], "est :")
  73.     chemin = [sommets[-1]]
  74.     indice = len(sommets) - 1
  75.     while indices_precedents[indice] != -9999:
  76.         indice = indices_precedents[indice]
  77.         chemin.append(sommets[indice])
  78.     print(" --> ".join(reversed(chemin)))
  79.  
  80. # Programme principal
  81. sommets = ['G', 'Ha', 'L', 'A', 'B', 'He', 'O', 'E', 'S']
  82. matrice = creer_represetation_matricielle()
  83. afficher_matrice(matrice, sommets)
  84. distances, indices_precedents = algo_dijkstra(matrice)
  85. afficher_distance_minimales(distances, indices_precedents, sommets)
  86. afficher_chemin_minimales(distances, indices_precedents, sommets)
  87.  
Success #stdin #stdout 1.18s 51744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
La matrice est:
_____________________________________________
          G         Ha        L         A         B         He        O         E         S         
_____________________________________________
G         -         680       360       300       -         -         -         -         -         
Ha        -         -         -         -         90        100       -         -         -         
L         -         -         -         -         -         -         -         -         -         
A         -         160       -         -         -         -         720       220       -         
B         -         -         -         190       -         110       210       -         -         
He        -         -         -         -         -         -         120       -         400       
O         -         -         -         -         -         -         -         -         130       
E         -         -         -         -         -         -         630       -         550       
S         -         -         -         -         -         -         -         -         -         

Les longueurs minimales à partir de G sont :
_____________________________________________
G         Ha        L         A         B         He        O         E         S         
_____________________________________________
-         460:A     360:G     300:G     550:Ha    560:Ha    680:He    520:A     810:O     

Le chemin critique allant de G à S est :
G --> A --> Ha --> He --> O --> S
https://ideone.com/mlaVKg
language:
Python 3 (python  3.12)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!