Bonjour,

J'ai un projet en python à réaliser dans lequel je dois optimiser les temps de trajet d'une compagnie de taxi dans une ville. On a 16 lieux, A représentant la compagnie de taxi et P représentant l'aéroport.
La première question est simple, il s'agit de déterminer le plus court chemin de A à P. Ensuite, je dois déterminer le plus court chemin entre tous les points de la ville.
Le problème est que je n'arrive pas trop à créer la fonction permettant de calculer d'un coup tous les plus courts chemins (y a une trentaine d'arêtes)

Merci !

Dijkstra calcule les plus courts chemins allant d'une source à tous les autres sommets du graphe, du coup si tu as déjà implémenté Dijkstra tu as juste à itérer ça en partant de chaque source possible.

Sinon il existe cet algorithme qui calcule directement tous les plus courts chemins : https://fr.wikipedia.org/wiki/Algorithme_de_Floyd-Warshall

Wow, merci beaucoup pour Floyd Warshall
J'ai fini par réussir à l'implémenter mais les plus courts chemins qu'il me donne sont toujours inférieurs à 1pt du réel résultat, sauf pour les arêtes directes