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

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.

-
Are you intending edge weightings to be multiplicative? – Peter Taylor Dec 6 '11 at 10:59
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. – Kim Burgess Dec 6 '11 at 12:57
@PeterTaylor: Would it matter if they were multiplicative? They have exact same semantics as additive (provided they are positive) by applying a logarithm. Or is it something more complicated behind it? – herby Dec 8 '11 at 8:00
@herby, good point, hadn't thought of that. hangs head in shame – Peter Taylor Dec 8 '11 at 9:09

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.

-
I believe the graph displayed above is a simpl(ified) example and in real life there may often be multiple alternative paths between two nodes (formats), i.e. you may not count on the graph always being a tree. – Péter Török Dec 6 '11 at 8:53
Suitably implemented, Dijkstra's algorithm would be O(n) too, although more complicated and still overkill. – Peter Taylor Dec 6 '11 at 8:56
@PéterTörök: In that case, yes. Only the asker knows for sure. But when it is a tree, bfs is enough (and dead simple). – herby Dec 6 '11 at 9:09
@PeterTaylor: Interesting. Any source, please? – herby Dec 6 '11 at 9:10
@PéterTörök is correct. See edited question. – Kim Burgess Dec 6 '11 at 9:21

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.

-
+1: As well, IIRC, the heuristic has to always estimate a cost that is worse than the actual cost in order for it to guarantee an optimal path. In the worst case, if you can't get the heuristic right, just return 0 from the heuristic and you've got dijkstra's algorithm. – Steve Evers Dec 7 '11 at 4:04