Shortest path in a weighted graph with coloured edges

Question

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$

Answer 1

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.