Tester les plus courts chemins iOS : poids, accès et dépassements

La navigation hors ligne, les itinéraires sur un campus ou la planification de parcours dans une application peuvent nécessiter un calcul de plus court chemin directement dans le client iOS. Un algorithme peut donner les bonnes distances sur des exemples ordinaires, puis renvoyer des résultats plausibles mais faux face à un cycle de poids nul, à des sommets déconnectés ou à des poids très élevés. Une petite implémentation de référence en Swift, claire et exécutable sur un Mac cloud, permet de repérer les régressions algorithmiques plus facilement qu’en sélectionnant simplement des itinéraires dans l’interface.

Définir d’abord le contrat du graphe et des résultats

Nous utilisons ici un graphe orienté dont les sommets sont numérotés à partir de zéro et dont les arcs portent des poids Int64 positifs ou nuls. Pour représenter une route à double sens, il faut ajouter explicitement un arc dans chaque direction. La distance du sommet de départ à lui-même vaut zéro ; un sommet inaccessible reçoit nil. Ni zéro ni la valeur entière maximale ne doivent servir à signaler l’inaccessibilité.

À l’entrée, il faut vérifier le sommet de départ, les sommets d’arrivée des arcs et l’absence de poids négatifs, y compris dans les sous-graphes inaccessibles depuis le départ. Les arcs parallèles sont autorisés : l’algorithme doit retenir le plus court. Les boucles sur un même sommet sont également admises, mais ne doivent pas provoquer de mises à jour sans fin.

Dijkstra repose sur des poids positifs ou nuls. Ne « corrigez » pas les données en remplaçant les valeurs négatives par zéro : cela changerait le problème métier lui-même.

Si le graphe utilise des unités entières, comme des mètres ou des millisecondes, fixez la précision lors de la conversion des données. Ne calculez pas d’abord les distances en virgule flottante pour les tronquer ensuite en entiers : les tests ne compareraient plus le même graphe.

Écrire un modèle de référence facile à relire

L’implémentation ci-dessous sélectionne les sommets par balayage, avec une complexité temporelle de O(V²＋E) et une complexité spatiale de O(V). Elle convient à la validation de petits graphes, mais ne permet pas de démontrer les performances de l’algorithme de production sur de grandes cartes. Enregistrez ce code dans shortest-path.swift, puis ajoutez les cas de test suivants au même fichier.

enum GraphError: Error {
    case invalidVertex
    case negativeWeight
    case overflow
}

struct Edge {
    let to: Int
    let weight: Int64
}

func distances(
    _ graph: [[Edge]],
    from source: Int
) throws -> [Int64?] {
    guard graph.indices.contains(source) else {
        throw GraphError.invalidVertex
    }

    for edges in graph {
        for edge in edges {
            guard graph.indices.contains(edge.to) else {
                throw GraphError.invalidVertex
            }
            guard edge.weight >= 0 else {
                throw GraphError.negativeWeight
            }
        }
    }

    var result = Array<Int64?>(repeating: nil, count: graph.count)
    var settled = Array(repeating: false, count: graph.count)
    result[source] = 0

    for _ in graph.indices {
        var selected: Int?
        for vertex in graph.indices where !settled[vertex] {
            guard let value = result[vertex] else { continue }
            if let current = selected {
                if value < result[current]! {
                    selected = vertex
                }
            } else {
                selected = vertex
            }
        }

        guard let vertex = selected else { break }
        settled[vertex] = true
        let base = result[vertex]!

        for edge in graph[vertex] where !settled[edge.to] {
            let (candidate, overflow) =
                base.addingReportingOverflow(edge.weight)
            guard !overflow else { throw GraphError.overflow }

            if let previous = result[edge.to] {
                if candidate < previous {
                    result[edge.to] = candidate
                }
            } else {
                result[edge.to] = candidate
            }
        }
    }

    return result
}

Ce modèle ne renvoie que les distances et ne conserve pas les prédécesseurs, afin de ne pas mêler la reconstruction des chemins à la validation des distances. À distance égale, les sommets sont traités dans l’ordre de leur numéro pour faciliter la reproduction des résultats, mais la logique métier ne doit pas dépendre de cet ordre.

Couvrir les cas limites avec des exemples fixes

Ajoutez d’abord un petit graphe contenant des arcs parallèles, un cycle de poids nul et un sommet isolé. Écrivez directement les résultats attendus, sans les générer à l’aide d’un autre algorithme lui-même à tester.

let graph: [[Edge]] = [
    [Edge(to: 1, weight: 9), Edge(to: 1, weight: 2)],
    [Edge(to: 2, weight: 0)],
    [Edge(to: 1, weight: 0), Edge(to: 3, weight: 3)],
    [],
    []
]

let actual = try distances(graph, from: 0)
precondition(actual == [0, 2, 2, 5, nil])

let singleton = try distances([[]], from: 0)
precondition(singleton == [0])

Ajoutez ensuite des cas distincts pour un graphe vide, un sommet de départ hors limites, un arc de poids négatif, un sommet d’arrivée hors limites et une distance maximale valide. Chaque cas d’erreur doit vérifier séparément le type d’erreur précis attendu, plutôt que de considérer n’importe quelle exception comme un succès.

let largest = try distances([
    [Edge(to: 1, weight: Int64.max)],
    []
], from: 0)
precondition(largest[1] == Int64.max)

do {
    _ = try distances([
        [Edge(to: 1, weight: Int64.max)],
        [Edge(to: 2, weight: 1)],
        []
    ], from: 0)
    preconditionFailure("Expected overflow")
} catch GraphError.overflow {
}

La politique retenue ici est prudente : dès qu’une opération de relaxation effectivement exécutée provoque un dépassement de capacité, toute la requête échoue, même si le graphe contient un autre chemin plus court. Si l’implémentation de production adopte une autre politique, il faut lui définir un contrat distinct ; on ne peut pas comparer directement les comportements d’erreur des deux implémentations.

Vérifier les propriétés, pas seulement quelques réponses

En complément des résultats fixes, vérifiez trois types de transformations. Mélanger l’ordre des arcs de chaque sommet ne doit pas changer les distances ; ajouter un arc parallèle de poids supérieur ne doit pas améliorer le résultat ; ajouter un sous-graphe valide, déconnecté du graphe initial, doit laisser les résultats des sommets existants inchangés. Pour ces tests de propriétés sur les distances, limitez les poids afin que toutes les additions concernées restent représentables.

Ces propriétés permettent de détecter des défauts tels qu’une dépendance à l’ordre des données ou un écrasement incorrect des arcs parallèles. Si vous générez de petits graphes aléatoires, fixez la graine du générateur et, en cas d’échec, conservez la liste d’adjacence complète, le sommet de départ et les résultats attendus. Un simple numéro d’échec difficile à reproduire ne suffit pas.

Si l’interface de production renvoie aussi un itinéraire, il faut en plus le parcourir arc par arc pour le vérifier : les sommets de départ et d’arrivée doivent être corrects, chaque arc doit réellement exister et la somme des poids doit être égale à la distance annoncée. En présence d’arcs parallèles, mieux vaut renvoyer des identifiants d’arcs qu’une simple suite de sommets. Plusieurs chemins peuvent avoir la même longueur minimale ; n’imposez donc pas une comparaison avec une chaîne de prédécesseurs particulière.

Intégrer la validation sur le nœud cloud

Sur un nœud physique VMFly, commencez par consigner la version de la chaîne d’outils, puis compilez et exécutez le programme. Les commandes suivantes ne dépendent pas du simulateur et peuvent être placées avant la compilation complète de l’application.

set -eu
xcrun swiftc --version
mkdir -p .build
xcrun swiftc -Onone shortest-path.swift \
  -o .build/shortest-path-check
.build/shortest-path-check

L’exemple utilise precondition pour qu’un résultat incorrect entraîne une sortie avec un code non nul. Ne le remplacez pas par assert, que les optimisations de compilation en mode release peuvent supprimer, et n’utilisez pas non plus -Ounchecked, qui élimine ces vérifications. Dans le projet réel, intégrez ensuite les mêmes cas à la cible de tests en appelant le point d’entrée du calcul de chemins de production.

Le pipeline doit conserver au minimum le graphe ayant échoué, la version de la chaîne d’outils et le tableau des distances obtenues. Gardez cet ordre de validation : validité des entrées, résultats des distances, vérification des itinéraires, puis respect du budget de performance. Une fois les contrôles de correction validés, mesurez séparément le temps de calcul sur les grands graphes. Une exécution « très rapide » ne doit pas masquer une erreur dans le traitement des sommets inaccessibles ou dans la sémantique des dépassements de capacité.

Questions fréquentes