import numpy as np

# Matrice d'adjacence M associée au graphe G

M=np.array([[np.inf,7,np.inf,np.inf,14,np.inf,np.inf,np.inf],
           [np.inf,np.inf,8,np.inf,np.inf,np.inf,np.inf,np.inf],
           [np.inf,np.inf,np.inf,6,np.inf,np.inf,np.inf,np.inf],
           [18,np.inf,np.inf,np.inf,np.inf,11,np.inf,np.inf],
           [np.inf,np.inf,np.inf,np.inf,np.inf,19,np.inf,np.inf],
           [np.inf,np.inf,np.inf,np.inf,np.inf,np.inf,4,13],
           [np.inf,np.inf,5,np.inf,np.inf,np.inf,np.inf,8],
           [np.inf,np.inf,9,np.inf,np.inf,np.inf,np.inf,np.inf]])

print("M=",M)

# Exercice 1

def RFW(M):
    L=M.copy() # Copie profonde L de la matrice M initiale
    n= ...
    for k in range(...): # On fait l'étape n°k pour k entre ... et ...
        for i in range(...): # on parcourt les lignes de L
            for j in range(...): # on parcourt un à un les termes de la ligne i de M
            # Si le chemin le plus court passe par .......... alors on remplace dans L
                if .......... :
                    ............
    return L

print("L=",RFW(M))


#%%

# Exercice 2


#%%

# Exercice 3

def RFW2(M):


#%%

# Exercice 4

def Itineraire(dep,arr):   


#%%

# Exercice 5

# Question 0

D=np.load('Dico_Metro-Numero.npy',allow_pickle=True).flat[0] # Dictionnaire arrêt de Métro:numéro
M=np.load("Matrice_distances_Metro.npy",allow_pickle=True) # Matrice des distances entre station voisine de métro


#%%

# Question 1



#%%

# Question 2



#%%

# Question 3

import time
tac=time.time()

# Commandes dont on veut mesurer la durée

tic=time.time()
duree=tic-tac
print("L'algorithme RFW a pris",duree,"s")

#%%

# Question 3

dep="Anvers"
arr="Vavin"


#%%

# Question 4


#%%

# Question 5

dep="Vavin"
arr="Anvers"

#%%

# Question 6