Une feuille de service permet de passer par plusieurs lieux avant de rejoindre une dernière table. Léa veut choisir un seul parcours, avec le plus petit score total donné par les flèches. Elle ne demande pas de couvrir chaque liaison, ni de prévoir les choix simultanés de plusieurs convives. Les scores sont fixés avant sa comparaison. Une route découverte rapidement peut donc être examinée sans que son résultat devienne aussitôt définitif pour toutes les autres possibilités.
Tous les lieux, les flèches et les nombres sont créés. Les scores sont des points abstraits, pas des durées, des distances ou des sommes à payer. Un nombre négatif diminue une addition ; il ne fait pas parcourir un couloir en un temps négatif. Chaque flèche possède un sens et ne donne pas gratuitement son retour. Les parcours restent des suites finies. Les répétitions seront autorisées dans les branches où une boucle existe, sauf lorsqu'une demande les interdit expressément.
MapTiler présente un catalogue de cartes.
Mapbox présente des cartes.
TomTom présente des cartes et des services de localisation.
Ces pages ont été lues pour cette catégorie seulement. Aucun score, trajet réel ou méthode de calcul n'en est repris.
Un premier chemin disponible n'est pas encore le meilleur
Le dessin donne S comme départ et T comme fin. S vers A porte deux points, S vers B cinq, B vers A moins quatre, A vers T deux et B vers T quatre. Il n'existe aucune autre flèche dans cette première feuille. S, A, T vaut quatre. S, B, T vaut neuf. S, B, A, T vaut trois, puisque cinq moins quatre puis deux donne trois. Léa retient cette dernière suite pour sa remise et conserve ses trois flèches dans leur ordre.
Une première méthode de préparation traitait comme définitif le lieu encore ouvert portant le plus petit score provisoire. Après S, A recevait deux et B cinq. A était donc fermé à deux ; son passage vers T donnait quatre. T, plus petit que le cinq de B, était fermé à son tour. Léa compare cette fin annoncée de quatre au parcours S, B, A, T effectivement rempli à trois. Elle retire la déclaration de minimum attachée au premier arrêt, sans retirer la route de quatre des parcours permis.
Examiner B ensuite aurait donné un score un pour rejoindre A, grâce à cinq moins quatre. La fermeture de A à deux empêchait précisément cette correction de revenir jusqu'à T. Le défaut n'était pas une erreur dans l'addition deux plus deux : quatre était bien le score de S, A, T. Léa rouvre A, inscrit un pour son accès par B, puis reprend A vers T avec deux supplémentaires. T reçoit trois. Elle choisit cette route entière, plutôt que de corriger seulement le nombre de T en laissant ses deux anciennes flèches sous le nouveau résultat.
Des flèches non négatives permettent une autre justification de fermeture
Léa examine une feuille séparée où B vers A porte un point au lieu de moins quatre. Les autres flèches gardent leurs valeurs. S, A, T vaut toujours quatre ; S, B, A, T vaut huit. Dans cette feuille, fermer A à deux avant B à cinq ne peut perdre l'amélioration rencontrée précédemment : le passage de B à A ajoute désormais un, il ne retire plus quatre. Léa retient S, A, T à quatre pour cette comparaison indépendante.
La justification ne se limite pas au seul un donné à B vers A. Lorsque toutes les flèches sont non négatives, un parcours meilleur vers un lieu choisi devrait passer par un premier lieu encore ouvert. La partie déjà parcourue jusqu'à ce premier lieu ne coûterait pas davantage que le parcours entier, puisque la suite ne peut plus diminuer son score. Sa proposition provisoire aurait donc été au plus aussi petite que ce meilleur total. Elle aurait empêché de sélectionner un lieu portant un nombre strictement plus grand comme prochain minimum définitif.
Dans la feuille signée, ce contrôle se brise à un endroit concret. B reçoit cinq, plus que le deux provisoire de A, mais la continuation de B vers A retire quatre et conduit à un. Le score du préfixe jusqu'à B est plus grand que le score du parcours qui continue depuis lui. Léa ne transporte donc pas dans cette feuille la justification de fermeture de la version non négative. Elle conserve la réussite à quatre dans l'autre version, puis choisit une préparation qui laisse les corrections se propager dans la version signée.
Limiter le nombre de passages donne des étapes de comparaison explicites
Pour préparer la feuille signée sans fermeture prématurée, Léa classe maintenant les réponses par nombre maximal de flèches. Avec zéro passage, seul S est atteint, pour zéro point. Avec une flèche, A peut être atteint pour deux et B pour cinq ; T ne l'est pas encore. Elle conserve T comme inaccessible à cette étape, pas comme une table rejointe avec zéro. Le nombre zéro appartenait au départ resté sur place, et ne fournit aucun chemin vers T.
Avec deux flèches au plus, A peut recevoir un par S, B, A. T peut recevoir quatre par S, A, T, ou neuf par S, B, T ; Léa conserve quatre. Les meilleurs scores de A et T à cette étape ne décrivent pourtant pas les étapes d'un seul même parcours. L'accès à A pour un utilise déjà deux flèches, alors que le T pour quatre utilisait l'ancien accès direct à A. Léa garde une liste de témoins pour retrouver la quantité de passages portée par chaque résultat, au lieu de joindre toutes les meilleures cases comme si elles formaient une route commune.
Avec trois flèches au plus, elle reprend le un de A obtenu dans la ligne précédente et ajoute A vers T pour deux. T reçoit trois avec S, B, A, T. Léa retire quatre du résultat actif de cette nouvelle étape, mais garde son témoin S, A, T dans la comparaison limitée à deux flèches. Le choix n'avait pas trouvé un moyen de réaliser trois en deux passages : il a utilisé un passage supplémentaire pour obtenir un score plus petit. Les deux limites de nombre conservent leurs réponses différentes dans la feuille.
Reprendre la ligne précédente évite de changer le sens d'une étape
Pour remplir la ligne de trois passages, Léa conserve d'abord chaque résultat déjà disponible avec deux. Elle examine ensuite chaque flèche et la fait suivre d'un accès disponible dans la ligne de deux, en ajoutant un passage. Toute route de trois passages au plus appartient à l'une de ces possibilités : elle en utilise au plus deux, ou elle termine par une dernière flèche après un préfixe d'au plus deux. La comparaison couvre donc les parcours de la demande, sans supposer qu'un signe négatif interdirait de regarder une flèche.
Camille avait proposé de mettre à jour les cases sur une seule ligne pendant leur lecture. En examinant S vers B, puis B vers A, puis A vers T, elle pourrait propager successivement cinq, un et trois dans le même tour. Ces nombres sont corrects comme scores de parcours disponibles, mais T utilise alors trois flèches. Léa refuse de nommer cette ligne résultat avec une seule flèche. Elle choisit de garder la ligne précédente séparée pour sa demande portant sur le nombre de passages, plutôt que d'attribuer à un tour de remplissage un nombre que l'ordre des flèches peut déjà dépasser.
Un autre ordre d'examen commencerait par les flèches arrivant à T, avant de donner leurs résultats à A et B. Dans un premier tour sur une ligne initialement vide hors S, T ne recevrait encore aucun accès ; A et B seraient remplis ensuite. Il faudrait un tour suivant pour propager leur information vers la fin. Léa conserve ainsi deux parcours de préparation qui ne donnent pas la même avancée par tour. La séparation des lignes selon les passages retire cette dépendance à l'ordre de lecture : chaque nouvelle ligne reprend seulement les résultats que la précédente avait réellement conservés.
Vérifier une limite par des nombres attachés aux lieux
Léa dispose enfin d'une autre preuve pour la feuille initiale signée. Elle donne zéro à S, un à A, cinq à B et trois à T. Pour chaque flèche, le nombre du lieu d'arrivée doit être au plus égal au nombre du départ plus le score de la flèche. S vers A autorise un au plus deux ; S vers B donne cinq au plus cinq ; B vers A donne un au plus cinq moins quatre. A vers T donne trois au plus un plus deux. B vers T donne trois au plus cinq plus quatre. Les cinq contrôles passent.
Ces inégalités donnent une borne pour tout parcours de S à T. À chaque passage, le score de la flèche est au moins la différence entre les deux nombres des lieux. En additionnant le long d'une route, les nombres des lieux intermédiaires s'annulent avec leur occurrence suivante. Il reste au moins le nombre de T moins celui de S, soit trois. Léa possède également le parcours S, B, A, T à trois. La borne et la réalisation se rencontrent ; elle peut annoncer le minimum sans transformer les nombres attachés aux lieux en scores de cinq routes qu'elle aurait effectivement parcourues.
Le premier relevé qui fermait A à deux et T à quatre ne fournit pas ce certificat. Sur B vers A, il demanderait que deux soit au plus égal à cinq moins quatre, donc à un. Ce contrôle échoue. Léa situe ainsi la case qu'il faut corriger avant de reprendre la propagation jusqu'à T. L'échec d'une inégalité ne suffirait pas, à lui seul, à dire qu'aucune autre preuve de quatre existe ; ici, le témoin à trois a déjà réfuté quatre comme minimum. Le certificat corrigé explique ensuite pourquoi trois ne sera pas battu dans la feuille donnée.
Une boucle de score négatif peut retirer l'existence d'un minimum
Une branche nouvelle ajoute A vers B avec un point, tout en gardant B vers A à moins quatre. La boucle A, B, A vaut donc moins trois. Léa peut rejoindre A depuis S, faire cette boucle, puis rejoindre T. S, A, T donnait quatre ; avec un tour de boucle avant T, le score devient un ; avec deux tours, il devient moins deux. Chaque route reste finie et respecte le sens des flèches. Les répétitions sont autorisées dans cette branche, et aucun nombre maximal de passages n'est encore donné.
À chaque proposition remise, Léa peut ajouter un tour de cette boucle et gagner trois points vers le bas. Elle retire donc l'annonce d'un plus petit score atteint par une route finie. Choisir un score négatif très bas ne ferme pas la comparaison : la même route peut être prolongée d'un tour supplémentaire avant de partir vers T. Léa ne remet pas une route dite infinie, puisque ses parcours doivent rester finis. Elle conserve la constatation précise qu'il n'existe aucun minimum fini sous cette permission de répétition, avec une famille de routes qui améliore toujours la précédente.
Les nombres attachés aux lieux ne peuvent fournir le certificat précédent sur cette boucle. A vers B exigerait que le nombre de B soit au plus celui de A plus un. B vers A exigerait que le nombre de A soit au plus celui de B moins quatre. Les deux contrôles réunis demanderaient que zéro soit au plus moins trois. Léa refuse donc le tableau prétendant valider toutes ces flèches par un certificat fini. L'obstacle ne dépend pas d'une mauvaise origine choisie pour ses nombres : les deux nombres intermédiaires ont disparu dans cette addition des contraintes.
Une limite de passages rétablit une question finie sans effacer la boucle
L'hôte pose maintenant quatre flèches au plus dans la branche avec A vers B. Léa compare les routes sous cette nouvelle limite. S, A, B, A, T utilise quatre flèches et vaut un. S, B, A, T en utilise trois et vaut trois ; S, A, T en utilise deux et vaut quatre. La comparaison par lignes jusqu'à quatre passages donne un comme meilleur score accessible à T. Léa remet la route de quatre, sans l'intituler meilleur parcours sans limite : sa fermeture dépend du nombre maximal expressément ajouté.
Avec cinq flèches au plus dans une autre demande, S, B, A, B, A, T devient possible et vaut zéro. Léa remplace donc la route de quatre par celle-ci pour la nouvelle limite. Elle ne donne pas zéro à la route S, A, B, A, T en conservant ses anciennes flèches. La baisse d'un vient du nouvel accès par B, suivi du tour permis avant T. La feuille garde les scores un et zéro auprès de leurs limites respectives. Augmenter le nombre autorisé ne retire pas la boucle négative ; il ouvre une nouvelle portion finie des routes que cette boucle peut engendrer.
Interdire au contraire de revenir dans un lieu déjà visité produit une autre question. La boucle A, B, A est alors interdite, même si ses flèches existent dans le dessin. Les routes simples de S à T restent S, A, T ; S, B, T ; S, B, A, T ; et S, A, B, T. Leurs scores sont quatre, neuf, trois et sept. Léa retient S, B, A, T à trois. Cette sélection n'est pas la route à un obtenue avec quatre passages : celle-ci répétait A. La permission concerne les lieux revisités, et ne peut être remplacée par une simple annotation sur le score final.
Une boucle atteignable peut rester sans route vers la fin demandée
Une branche séparée retrouve les cinq flèches initiales, sans A vers B. Elle ajoute S vers X pour zéro, X vers Y pour moins deux, puis Y vers X pour un. La boucle X, Y, X vaut moins un et peut être atteinte depuis S. Aucune flèche ne permet pourtant de quitter X ou Y vers A, B ou T. Léa peut obtenir des scores de plus en plus petits dans cette partie du dessin ; aucun de ces parcours ne rejoint la fin T qui lui a été demandée.
Elle conserve S, B, A, T et son minimum trois pour cette destination. Une proposition voulait déclarer la recherche entière sans minimum dès qu'une boucle négative accessible apparaissait quelque part. Léa la retire pour T. Toute route qui entre dans X ou Y y reste ; toute route qui atteint T se trouve donc dans le premier réseau, dont le certificat à trois demeure valable. Léa ne nie pas les scores sans borne de X et Y. Elle les rattache aux destinations pour lesquelles ils peuvent réellement fournir des parcours, au lieu d'en faire un résultat automatiquement applicable à chaque lieu du dessin.
Ce choix exige les deux accès pour juger une boucle : pouvoir l'atteindre depuis S, puis pouvoir en repartir jusqu'à T. La première boucle A, B, A possédait les deux. La nouvelle boucle X, Y, X ne possède que le premier. Léa prépare un relevé des lieux qui permettent encore de rejoindre T et y conserve S, A, B et T. Elle ne marque pas X et Y comme oubliés ou inexistants ; ils sont retirés seulement du sous-dessin utile à cette question de fin. Le filtrage a gardé les routes recherchées tout en laissant la branche sans issue dans le dossier général.
Ajouter une sortie change le rôle de la boucle déjà présente
Léa reçoit ensuite une flèche nouvelle Y vers B, de score deux. La boucle X, Y, X peut désormais rejoindre T par B puis A. Elle prépare S, X, Y, B, A, T : zéro moins deux, puis deux, moins quatre et deux donne moins deux. Revenir de Y vers X puis Y avant de sortir vers B retire encore un point. La route avec ce tour supplémentaire vaut moins trois. Chaque tour additionnel peut maintenant améliorer un parcours qui atteint effectivement T, ce qui n'était pas possible avant la sortie ajoutée.
Léa retire donc le minimum trois du résultat actif de cette nouvelle feuille sans limite de passages. Elle conserve les deux modifications qui l'ont rendu inapplicable : X et Y possédaient déjà la boucle négative, mais Y dispose maintenant de la sortie vers B. Elle ne prétend pas que le score de X vers Y aurait changé. La même boucle a obtenu une continuation vers la destination demandée. Le relevé des lieux permettant T doit donc accueillir X et Y ; reprendre l'ancien filtrage les laisserait encore dehors alors qu'ils portent précisément les nouvelles routes à examiner.
Un certificat peut être limité au sous-dessin utile
Dans la feuille où X et Y n'avaient pas de sortie, Léa ne pouvait pas donner des nombres finis satisfaisant les inégalités de toutes les flèches : la boucle négative l'interdisait déjà dans cette partie. Elle pouvait néanmoins garder le certificat zéro, un, cinq, trois sur S, A, B et T. Elle vérifie les cinq flèches de ce sous-dessin et remet S, B, A, T comme témoin. La preuve porte sur toutes les routes qui terminent à T, puisque aucune d'elles ne traverse la partie retirée. Elle n'annonce pas un tableau global certifiant aussi les destinations X et Y.
Cette portée doit rester dans le relevé remis. Camille avait conservé le titre « meilleur score pour chaque lieu » au-dessus du petit tableau. Léa le remplace par « borne pour les parcours finissant à T » et garde la mention de la boucle sans issue. Avec la sortie Y vers B, cette petite preuve ne serait plus suffisante : des routes passant par X et Y peuvent maintenant finir à T, tandis que ces deux lieux ne portent aucun nombre compatible avec leur boucle. La restriction valable dans l'ancienne feuille ne peut donc pas être appliquée à la nouvelle en conservant seulement ses quatre nombres.
La feuille distingue ainsi un parcours découvert, une borne vérifiée, une limite de passages et l'existence d'un minimum. Léa peut conserver le score trois pour une destination tout en reconnaissant une boucle négative ailleurs, ou retirer toute promesse de minimum lorsqu'une sortie rend cette boucle pertinente. Ses routes et ses preuves restent celles d'un dessin créé ; les trois pages cartographiques consultées ne certifient aucun déplacement ni aucune performance réelle de calcul.