Simplification d'une matrice de booléens
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:
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 !
