I'm in the process of developing a signal management and routing module for an integrated audiovisual system and am designing it with the intent of being as flexible as possible across different signal distribution networks. The intent of the module is to handle routing across a number of stacked matrix switchers1 and handle necessary format conversion.
The best solution I've explored at this point is to map out the network to a graph with discrete vertices for each signal type supported by the switchers and which are then joined via nodes representing the video processors that handle format conversion.
Colours represent signal formats.
Round nodes are either switchers, sources or sinks.
Square nodes are video processors which perform format conversion.
From there I can use an implementation of Dijkstra's algorithm to identify the path that has to be formed in order to get input X to output Y. This should allow the data about the input / output configuration of all the switchers and processors to be passed in and the module adapt accordingly.
Is this an appropriate solution or is there an alternative approach that may be worth investigating?
1 aka 'crossbar switch', a video router with M input x N outputs that supports one-to-many connections. Each phsyical device may handle multiple signal formats and may or may not be capable of performing any format conversion.
edit: As mentioned by Péter Török, the graph will not necessarily be a tree, the diagram is a simple example to illustrate the idea. When implemented in the 'real world' multiple paths may exist which offer varying levels of definition (DVI > VGA > component > composite) which I was planning to represent with edge weighting.
edit 2: Here's an slightly more comprehensive example with directivity indicated and showing a network consisting of two signal types. The initial example has been modified slightly so that each input and output on a device is defined as a discrete node as this will provide the data required to control matrix routing / input selection.
Best Answer
This is a tree, Dijkstra is O(n^2) overkill. Trivial O(n) breadth-first search is enough.
EDIT: Start the BFS in any node with degree at least two.
EDIT2: Since the graph is not guaranteed to be a tree, use Dijkstra, if you want to optimize a little, you can first "strip" the graph all the vertices of degree one (for them, the path is trivial), including those that happen to acquire degree one due to stripping their ex-neighbours, and do the Dijkstra on the rest (which is exactly the "non-tree" part).
Plus, I would say you want paths from every node to every other, don't you? Dijsktra's algorithm does only paths from one to all others. Maybe do Floyd-Warshall algorithm on the stripped rest. Of course, if the topology is very dynamic, it is best to do the (stripping and) Dijkstra, ad hoc.