La distance par les puissances

Exercice · niveau 3 (difficile) · mathématiques appliquées (ECG 1re année), chapitre 3 — Théorie des graphes · Analyse de réseaux, en Python

Énoncé

Écrire une fonction Python distance(A, i, j) qui renvoie la longueur du plus court chemin de $i$ à $j$ , ou $- 1$ s'il n'en existe pas, en calculant les puissances successives de $A$ . Pourquoi peut-on s'arrêter à $A^{n - 1}$ ?

Corrigé


def produit(A, B):
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n))
             for j in range(n)] for i in range(n)]

def distance(A, i, j):
    n = len(A)
    if i == j:
        return 0
    P = A                      # P vaut A^d au tour d
    for d in range(1, n):      # d = 1, 2, ..., n-1
        if P[i][j] > 0:
            return d
        P = produit(P, A)
    return -1

Pourquoi $A^{n - 1}$ suffit. Un plus court chemin ne repasse jamais par un même sommet : s'il le faisait, on pourrait supprimer la portion comprise entre les deux passages et raccourcir — ce qui contredirait la minimalité. Il visite donc des sommets deux à deux distincts, au plus $n$ , et emprunte au plus $n - 1$ arêtes.

Si $(A^{d})_{ij} = 0$ pour tout $d \leq n - 1$ , aucun chemin ne relie $i$ à $j$ , et $- 1$ est la bonne réponse.

C'est le même argument que dans la caractérisation de la connexité par $I + A + \dots + A^{n - 1}$ : au-delà de $n - 1$ , on ne découvre plus rien.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.