# Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ vertices and $M$ edges. Each edge has its own weight and colour. There are at most 10 different colours in the whole graph. Each time I traverse edges of different colour I have to pay an additional fee equal to $K$. Given two vertices $A$ and $B$, I want to find the shortest path between them.

For example, given a multigraph with 3 vertices, $K = 5$, and 3 edges: ($1\rightarrow 2$ of weight 3 and colour 1), ($1\rightarrow 2$ of weight 5 and colour 2), ($2\rightarrow 3$ of weight 2 and colour 2), weight of the shortest path is 12.

I would like to design an algorithm that would solve this problem in reasonable time. My first idea was to use Dijkstra's algorithm and for every vertex store an information about the edge from which I went into that vertex, but that strategy won't work for the example given above. So I don't have any other idea than brute-force search.

Constraints:

• $N \leq 10^5$
• $M \leq 10^5$
• $K \leq 10^5$
• Is the cost of a path the number of distinct colors in it, or the number of color alternations (i.e. using several edges of the same color in a row doesn't cost anything)? Apr 29, 2016 at 8:58
• Using edges of the same color doesn't cost anything. Cost of a path is sum of weights of the edges + K * number of color changes. Apr 29, 2016 at 15:04
• Cross-posted: cs.stackexchange.com/q/56688/755, stackoverflow.com/q/36808913/781723, mathoverflow.net/q/237582/37212. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. P.S. What's the context where you encountered this? Is this a programming contest question?
– D.W.
Oct 11, 2016 at 13:51

Replace each vertex $x$ by $C$ vertices $(x,c)$, where $C$ is the number of colors (actually you only need the colors that appear in edges adjacent to $x$), and connect these vertices by edges of weight $K$. Replace an edge $(x,y)$ of weight $w$ and color $c$ by an edge $((x,c),(y,c))$ of weight $w$.

You can now solve your problem by running Dijkstra's algorithm on the new graph $C^2$ times. You can optimize this approach so that you only need to run Dijkstra's algorithm once by adding two new vertices $A,B$ and connecting $A$ to the vertices $(A,c)$ with directed edges, and similarly connecting the vertices $(B,c)$ to $B$ with directed edges.