SDD Question 4 Juin 2013

1) PMax[1,5] = 25

2) Si il y a un cycle, cela pourrait créer un chemin de taille infini dans certaines
   conditions.

3) P_k[s,s'] = p ssi p est le poids d'un plus long chemin de s à s' sans passer par un sommet > k

En cours d'execution:
    A une étape disposer de P_k-1
    A l'étape suivante calculer P_k[s,s']=max{P_k-1[s,s'],(P_k-1[s,k]+P_k-1[k,s'])}

Initialisation: P_0[s,s'] = 0 si s = s' et P_0[s,s'] = M[s,s'] sinon (M[s,s'] vaut le poids de l'arc (s, s')
                si il n'y a pas d'arc entre s et s', M[s,s'] = -infini

Fin des calculs: quand k = n+1

Algorithme besoin de deux matrices P_old, P_new pour P_k-1 et P_k respectivement

4)

plus_long_chemin(G):
pour s allant de 1 à n:
    pour s' allant de 1 à n:
        P_old[s,s'] <- M[s,s']
pour s allant de 1 à n:
    P_old[s,s] <- 0
pour k allant de 1 à n:
    pour s allant de 1 à n:
        pour s' allant de 1 à n:
            P_new[s,s'] <- max{P_old[s,s'],(P_old[s,k]+P_old[k,s'])}
    pour s allant de 1 à n:
        pour s' allant de 1 à n:
            P_old[s,s'] <- P_new[s,s']
retourner P_old