A brute-force solution is to recursively compute a table of shortest distances between all couple of nodes, that use all sublists of colors.
Let's call $col(A, B)$ the color of $A-B$ edge.
At each step, the table is updated by taking each node $A$, each node $B \ne A$, and each sublist $L$ of different colors. The shortest distance $S(A, B, L)$ is updated by computing the minimum of:
- itself, and,
- for all neighbors $C$ of $A$, where $col(A, C) \in L$: $S(C, B, L-col(A, C)) + length(A, C)$.
And repeat until no value is modified.
Complexity is the product of:
- number of couples of nodes: $\frac {N(N-1)} 2$ if there are $N$ nodes;
- number of lists of different colors: $2^C-1$, if there are $C$ colors;
- number of operations per couple of nodes $\times$ color list; this can be crudely bounded by the maximum number of adjacent nodes to a node, times the network diameter (to allow for propagation).
The product of the two first items is equivalent to $2^C N^2 / 2$. This is also the space complexity, i.e. the number of values that have to be stored. For New York subway, the largest in the world, there are 472 nodes and 28 services, so that is 3E13, already too large for a PC but possible on a cluster. However the number of operations would be even larger and so probably not reasonably reachable. But the method is certainly usable on smaller networks.
