Discussion :

[condor_01]

Salut à tous,
Je compte concevoir un algorithme de routage puis le coder en C.
Le nom du type de routage est XY.
Voila le principe:
Etant donné une topologie (graphe) en 2D.
Pour aller d'une source S(xS,yS) à une destination D(xD,yD).
Prendre le chemin horizontalement (gauche ou droite) suivant yS jusqu'à arriver à xD (la colonne du point D)
Puis prendre le chemin verticalement (suivant xD) vers le point D jusqu'à arriver à yD.

Je veux concevoir un algorithme qui marche sur n'importe quel type de topologie. (grille, aléatoire ...)
Pour une topologie aléatoire ça sera un peu difficile. On peut tomber sur des points qui ne mènent pas verd D.

A savoir que j'ai en entrée la matrice d'adjascence de tout le graphe avec les coordonnées des points.

[FrancisSourd]

Tu n'as pas précisé le problème...

Le problème est-il de savoir si on peut atteindre D pour une source S donnée? De savoir quelles sont les paires sources destinations réalisables?

[condor_01]

En fait, je travaille sur des graphes connexes (On peut atteindre n'importe quel noeud à partir de n'importe quel noeud).
Donc la question si on peut atteindre ou non ne se pose pas.

Le problème c'est de déterminer le chemin le plus adéquat entre la source et la destination.

On peut avoir plusieurs chemins mais on doit aller par le chemin qui va mieux notre routage XY.
On part de la source en horizontal suivant le Y source (dans le cas d'un graphe quelconque il faut aller dans le chemin qui se rapproche le plus de Y source)
Puis quand on atteint X destination ou presque on part verticalement suivant le X destination.

Bien sur on aura à traiter les cas où le chemin ne mène pas à la destination et là il faut reboucler en éliminant le dernier noeuds de notre parcours.

[FrancisSourd]

Cela ressemble à un problème d'optimisation. Tu recherches le meilleur chemin XY. Il faudrait donc définir la qualité d'un chemin. Cela pourrait être le nombre de fois où l'on change de direction. Moins on change de direction, mieux c'est. Est-ce cela?