Bonjour,

Je travaille sur un logiciel de recherche d'itinéraires pour un réseau de bus.

Je dois d'abord calculer tous les chemins possibles pour aller d'un arrêt A à un arrêt B.

J'ai donc representer ce système par une matrice de booléen. Par exemple :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
 
   A B C D E F G H
A |0 1 0 0 0 1 0 0|
B |0 0 1 0 0 0 0 0|
C |0 0 0 0 0 0 0 0|
D |0 0 0 0 0 0 0 1|
E |0 0 0 0 0 0 1 0|
F |0 0 0 1 1 0 0 0|
G |0 0 0 0 0 0 0 0|
Cette matrice me sert à modéliser une sorte de graphe dirigé : de A je peux aller en B, de B je peux aller en C ...

Mais voilà, à part explorer tous les chemins possibles afin de voir si il arrive à mon arrêt final, je ne vois pas d'autres solutions.

Est ce qu'il y aurai une representation plus rapide et/ou moins couteuse en mémoire qui me permettrai de faire cette opération ?

Est ce qu'il y a une possibilité de réduire cette matrice ? ou est ce qu'il existe un algorithme qui permet de passer outre l'exploration de tous les chemins ?

Merci d'avance !