Is Dijkstra's algorithm an appropriate solution to this signal routing problem?

Question

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 switchers¹ 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?

_{¹ 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.

Answer 1

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.

Answer 2

You may be able to use A* (the more general form of Dijkstra's algorithm) for searching the graph in question. You mention the costs of the weightings in your comment:

Additive. The theory being this will allow it to be defined such that the higher the definition of the signal path, the lower the weighting. Edges which connect nodes that perform format conversion would then be given a weighting higher than that assigned to edges which connect non-conversion nodes. This would route the signal in it's native format if possible, only involving format conversion (and associated signal degradation and equipment utilisation) when necessary

If I understand it correctly, you want to find the lowest cost path path from the start to the goal. If you provide each node both an actual cost and an estimate (heuristic) to the goal (that is both admissible and consistent), then A* is guaranteed to provide an optimal solution. It might be overkill though, depending on how well I understand your problem.