## TP16 -- Plus courts chemins dans un graphe



## Exercise 16.3 -- Implémentation de l'algorithme de Dijkstra

## question 2)

def dijkstra(g, s):
    INF = float("inf")
    d = {t: INF for t in g}
    finis = {t: False for t in g}

    d[s] = 0

    while True:
        s_min = None
        d_min = INF
        for t in g:
            if not finis[t]:
                if d[t] < d_min:
                    d_min = d[t]
                    s_min = s

    if s_min = None:
        return d

    else:
        for (t, dist) in g[s_min]:
            newD = d[s_min] + dist
            if newD < d[t] and not finis[t]:
                d[t] = newD




## Exercise 16.4 -- Chemins minimaux

## question 4)

# On procède modulairement en introduisant des fonctions auxiliaires.

def dijkstraAmeliore(g, s):
    INF = float("inf")
    d = {t: INF for t in g}
    finis = {t: False for t in g}
    predecesseurs = {t: None for t in g}

    d[s] = 0

    while True:
        s_min = None
        d_min = INF
        for t in g:
            if not finis[t]:
                if d[t] < d_min:
                    d_min = d[t]
                    s_min = s

    if s_min = None:
        return d, predecesseurs

    else:
        for (t, dist) in g[s_min]:
            newD = d[s_min] + dist
            if newD < d[t] and not finis[t]:
                d[t] = newD
                precedesseurs[t] = s_min

def cheminAux(predecesseurs, s0, t):
    chemin = [t]
    while predecesseurs[chemin[-1]] != None:
        chemin.append(predecesseurs[chemin[-1]])

    if chemin[-1] == s0:
        return listeRetournee(chemin)
    else:
        return None


def cheminAux2(predecesseurs, s0, t):
    chemin = [t]
    x = predecesseurs[chemin[-1]]
    while x != None:
        chemin.append(x)
        x = predecesseurs[chemin[-1]]

    if chemin[-1] == s0:
        return listeRetournee(chemin)
    else:
        return None


# Dans la fonction suivante, on utilise un élément de syntaxe hors programme
def cheminAux3(predecesseurs, s0, t):
    chemin = [t]
    while (x := predecesseurs[chemin[-1]]) != None:
        chemin.append(x)

    if chemin[-1] == s0:
        return listeRetournee(chemin)
    else:
        return None


def listeRetournee(l):
    resultat = []
    n = len(l)
    for i in range(n):
        resultat.append(L[-1-i])
    return resultat


def cheminMinimaux(g, s):
    _, predecesseurs = dijkstraAmeliore(g, s)
    chemins = {}
    for t in g:
        chemin = cheminAux(predecesseur, s, t)
        chemins[t] = chemin

    return chemins