Cela semble compliqué ? Peut-être. Mais en fait, ce type de calcul est déjà utilisé dans un large éventail d’applications et de technologies dont nous dépendons pour nous repérer, comme Google Maps nous guide à travers les paysages et les villes, par exemple.

Aujourd’hui, des chercheurs du Département d’informatique de l’Université de Copenhague ont réussi à résoudre le problème du chemin le plus court à source uniqueune énigme qui laisse perplexe les chercheurs et les experts depuis des décennies.

« Nous avons découvert un algorithme qui résout le problème en un temps quasi linéaire, de la manière la plus rapide possible. C’est un problème algorithmique fondamental qui est étudié depuis les années 1950 et enseigné dans le monde entier. C’est l’une des raisons qui nous a poussés à résoudre », explique le professeur agrégé Christian Wulff-Nilsen, qui trouve clairement qu’il est difficile de laisser un problème algorithmique non résolu seul.

Calculs plus rapides pour le routage des voitures électriques

L’année dernière, Wulff-Nilsen a fait une autre percée dans le même domaine, qui a produit un résultat qui a abordé la façon de trouver le chemin le plus court dans un réseau qui change avec le temps. Sa solution à la récente énigme s’appuie sur ce travail.

Le chercheur pense que la résolution du problème du chemin le plus court à source unique pourrait ouvrir la voie à des algorithmes qui non seulement aident les voitures électriques à calculer l’itinéraire le plus rapide de A à B en un instant, mais le font de la manière la plus économe en énergie.

« Nous ajoutons une dimension que les algorithmes précédents n’avaient pas. Cette dimension nous permet de regarder ce que nous appelons des poids négatifs. Un exemple pratique de cela peut être en référence aux collines d’un réseau routier, ce qui est bon à savoir si vous avez une voiture électrique qui se recharge en descendant », explique Wulff-Nilsen.

Faits sur le problème du chemin le plus court à source unique

• Le but de le chemin le plus court de la source unique Le problème est de trouver les chemins les plus courts entre un nœud de départ donné et tous les autres nœuds d’un réseau.
• Le réseau est représenté sous la forme d’un graphe composé de nœuds et de connexions entre eux, appelées arêtes.
• Chaque tronçon a une direction (par exemple, cela peut être utilisé pour représenter des routes à sens unique), ainsi qu’un poids, qui exprime le coût de déplacement le long de ce tronçon. Si tous les poids des arêtes sont non négatifs, le problème peut être résolu en temps pratiquement linéaire avec un algorithme de Dijkstra classique.
• Le nouveau résultat résout le problème dans presque le même laps de temps que l’algorithme de Dijkstra, mais permet également des poids de bord négatifs.

« En principe, l’algorithme pourrait être utilisé pour avertir des acteurs, tels que les banques centrales, si des spéculateurs spéculent sur l’achat et la vente de diverses devises. Une grande partie de cela se produit aujourd’hui à l’aide d’ordinateurs. Mais parce que notre algorithme est si rapide, il pourrait être capable à utiliser pour détecter les failles avant qu’elles ne soient exploitées », explique Christian Wulff-Nilsen.

Le chercheur souligne que des systèmes de calcul à la fois de la monnaie et des trajets pour les voitures électriques existent déjà. Mais la résolution du problème du chemin le plus court à source unique a permis aux chercheurs de créer un superbe algorithme qui devient presque impossible à battre en termes de vitesse. En même temps, sa simplicité le rend facile à adopter pour les divers besoins de la société.

Honoré aux États-Unis

Le travail pour résoudre le problème n’est pas passé inaperçu. En effet, Christian Wulff-Nilsen et ses collègues ont déjà été contactés par des personnes du monde entier souhaitant les féliciter et en savoir plus sur la manière dont ils ont procédé.

Dans le même temps, l’article de recherche qui détaille leur découverte a été honoré d’un « prix du meilleur article » lors de la conférence FOCS (Foundation of Computer Science) à Denver, Colorado. Avec le STOC, c’est la conférence la plus prestigieuse en informatique théorique. La conférence FOCS s’est déroulée du 31 octobre au 3 novembre 2022.

« Des personnes du monde entier assistent à cette conférence pour voir les meilleurs résultats présentés », déclare Christian Wulff-Nilsen.

La recherche a été menée en collaboration entre Christian Wulff-Nilsen, du Département d’informatique, Danupon Nanongkai de l’Institut Max Planck et leur collègue américain, Aaron Bernstein de l’Université Rutgers.