be-graphes

I3MIIL11 - Bureau d’étude graphes

Répertoire de travail pour le bureau d’étude graphes de 3 MIC à l’INSA de Toulouse.

Remarques

Ce BE sera à priori fait sous VSCode (sous Ubuntu 20.04.02) au lieu d’Eclispe pour des raisons de praticité et d’habitudes (et aussi parce que je n’ai pas énormément de place sur mon disque dur). Jusqu’à présent ce choix ne m’a posé aucun problème hormis pour générer la docs.

Algorithme de Dijkstra (PCC)

Voici quelques résultats visuels de mon algorithme de Dijkstra en mode plus court chemin. D’abord sans observateurs, en vert sans contrainte de chemin, en rouge les routes autorisées aux voitures uniquement :

Exemple de résultat avec observateurs :

Test

Test avec oracle

Pour effectuer ces tests, j’ai utiliser le GUI pour créer un oracle avec Bellman Ford (un trajet entre l’aéroport LFBO et l’INSA de Toulouse sur la carte Haute Garonne). Notez que les tests peuvent être effectués avec n’importe quel autre oracle (il suffit de changer la carte et l’oracle).

On vérifie alors que la solution retournée est equivalente à l’oracle. Note: On vérifie pas l’égalité strict des chemins car (théoriquement) deux chemins optimaux peuvent co-exister.

Test d’optimalité (tests sans oracle)

Plusieurs tests sans oracle ont été implémentés :

• Test des sous-chemins : tous les sous-chemins doivent également suivre les mêmes nodes
• Test du vol d’oiseau : la distance en vol d’oiseau doit être plus courte que la distance obtenue
• Test de l’inégalité triangulaire : le même trajet passant par un troisième point doit être plus long ou égal en distance au chemin trouvé