N=11
Liste_A = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[3,8],[3,9],[7,8],[9,10],[0,10],[6,10],[6,7],[0,7]]
Duree = [[0,1,5],[1,2,3],[2,3,5],[3,4,2],[4,5,3],[5,6,4],[3,8,3],[3,9,2],[7,8,2],[9,10,3],[0,10,10],[6,10,11],[6,7,10],[0,7,10]]

D = sum(U[2] for U in Duree)

import numpy as np

# Question 1

def voisin_G(i):
    voisines=[]
    for metro in Liste_A:
        if metro[0] == i:
            voisines.append(metro[1])
        if metro[1] == i:
            voisines.append(metro[0])
    return voisines

# Question 2
"""
Considérons l'ensemble des durées des trajets entre i et j : c'est un ensemble d'entiers non vide (car G est connexe) et minoré (par 0). Il admet donc un minimum.
"""
# Question 3
"""
Par l'absurde, supposons qu'un des deux trajets i -> k ou k -> j n'est pas minimal (par exemple i -> k).
Dans le trajet i -> k -> j, on peut remplacer le trajet i -> k par un strictement plus court, ce qui donne un trajet de i -> j strictement plus court. Contradiction.
""" 
# Question 4
"""
ðmin(i,j) = min { ðmin(i,k) + ðmin(k,j) | k in G }
"""
# Question 5
Tinit = np.array([[D for i in range(N)] for i in range(N)])
for i in range(N):
    Tinit[i,i] = 0
for metro in Duree:
    i=metro[0]
    j=metro[1]
    d=metro[2]
    Tinit[i,j] = d
    Tinit[j,i] = d

# Question 6
def FW(T):
    TT=np.copy(T)
    for i in range(N):
        for j in range(N):
            l=[T[i,j]]
            for k in range(N):
                l.append(T[i,k]+T[k,j])
            TT[i,j] = min(l)
    return TT
    
    
# Question 7

for i in range(N-2):
    Tinit = FW(Tinit)
    
for i in Tinit:
    print(i)