L'algorithme de Dijkstra est-il une solution appropriée à ce problème de routage du signal?

Je suis en train de développer un module de gestion et d'acheminement des signaux pour un système audiovisuel intégré et je le conçois dans le but d'être aussi flexible que possible sur différents réseaux de distribution de signaux. L'objectif du module est de gérer le routage à travers un certain nombre de commutateurs matriciels empilés ¹ et de gérer la conversion de format nécessaire.

La meilleure solution que j'ai explorée à ce stade consiste à mapper le réseau sur un graphique avec des sommets discrets pour chaque type de signal pris en charge par les commutateurs et qui sont ensuite joints via des nœuds représentant les processeurs vidéo qui gèrent la conversion de format.

Les couleurs représentent les formats de signal. Les nœuds ronds sont soit des commutateurs, des sources ou des puits. Les nœuds carrés sont des processeurs vidéo qui effectuent une conversion de format.

De là, je peux utiliser une implémentation de l'algorithme de Dijkstra pour identifier le chemin qui doit être formé afin d'obtenir l'entrée X à la sortie Y. Cela devrait permettre aux données sur la configuration d'entrée / sortie de tous les commutateurs et processeurs de passer et le module s'adapte en conséquence.

Est-ce une solution appropriée ou existe-t-il une autre approche qui mérite d'être étudiée?

_{¹ aka «crossbar switch», un routeur vidéo avec M entrées x N sorties qui prend en charge les connexions un à plusieurs. Chaque appareil physique peut gérer plusieurs formats de signal et peut ou non être capable d'effectuer une conversion de format.}

edit: Comme mentionné par Péter Török, le graphique ne sera pas nécessairement un arbre, le diagramme est un exemple simple pour illustrer l'idée. Lorsqu'il est implémenté dans le «monde réel», il peut exister plusieurs chemins qui offrent différents niveaux de définition (DVI> VGA> composant> composite) que je prévoyais de représenter avec une pondération des bords.

edit 2: Voici un exemple un peu plus complet avec la directivité indiquée et montrant un réseau composé de deux types de signaux. L'exemple initial a été légèrement modifié afin que chaque entrée et sortie sur un périphérique soit définie comme un nœud discret car cela fournira les données requises pour contrôler le routage matriciel / la sélection d'entrée.

Ceci est un arbre, Dijkstra est O ( n ^ 2 ) exagéré. Une recherche en largeur Trivial O ( n ) en premier suffit.

EDIT: démarrez le BFS dans n'importe quel nœud avec un degré d'au moins deux.

EDIT2: Puisque le graphique n'est pas garanti d'être un arbre, utilisez Dijkstra, si vous voulez optimiser un peu, vous pouvez d'abord "dépouiller" le graphique tous les sommets de degré un (pour eux, le chemin est trivial), y compris ceux qui arrivent à acquérir le degré un en dépouillant leurs anciens voisins, et font le Dijkstra sur le reste (qui est exactement la partie "non arborescente").

De plus, je dirais que vous voulez des chemins de chaque nœud à l'autre, n'est-ce pas? L'algorithme de Dijsktra ne fait que des chemins de l'un à tous les autres. Peut-être faire l'algorithme Floyd-Warshall sur le reste dépouillé. Bien sûr, si la topologie est très dynamique, il vaut mieux faire le (stripping et) Dijkstra, ad hoc.

Vous pourrez peut-être utiliser A * (la forme plus générale de l'algorithme de Dijkstra) pour rechercher le graphique en question. Vous mentionnez les coûts des pondérations dans votre commentaire:

Additif. La théorie étant celle-ci permettra de la définir de telle sorte que plus la définition du chemin du signal est élevée, plus la pondération est faible. Les bords qui connectent des nœuds qui effectuent une conversion de format recevraient alors une pondération supérieure à celle attribuée aux bords qui connectent des nœuds sans conversion. Cela acheminerait le signal dans son format natif si possible, n'impliquant la conversion de format (et la dégradation du signal associée et l'utilisation de l'équipement) que si nécessaire

Si je comprends bien, vous voulez trouver le chemin du chemin le moins cher du début à l'objectif. Si vous fournissez à chaque nœud à la fois un coût réel et une estimation (heuristique) de l'objectif (à la fois admissible et cohérent), alors A * est garanti pour fournir une solution optimale. Cependant, cela pourrait être exagéré, selon la façon dont je comprends votre problème.