Shortest path in a weighted graph with coloured edges [closed]

Question

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. Given two vertices $A$ and $B$, I want to find the shortest path between them.

For example, given multigraph with 3 vertices, $K = 5$, and 3 edges:

• (1 -> 2 of weight 3 and colour 1)
• (1 -> 2 of weight 5 and colour 2)
• (2 -> 3 of weight 2 and colour 2)

The weight of the shortest path is 12.

I would like to design an algorithm that would solve this problem in considerable time. My first idea was to use Dijkstra 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 algorithm.

Constraints:

$N <= 10^5$,$M <= 10^5$,$K <= 10^5$

Answer 1

The problem can be reduced to an ordinary shortest path problem via vertex splitting where however, the number of generated vertices equals the degree of the original vertex and not two, as is commonly the case in the solution of certain flow problems.

The solution steps would be as follows:

• interprete your graph as a directed one, i.e. replace each undirected edge $e_{ij}$ with a pair of antiparallel arrows $a_{ij}$ and $a_{ji}$ of equal weight $w(a_{ij}) = w(a_{ji}) := w(e_{ij})$.

• associate each arc $a_{ij}$ with a "split vertex" $s_{ij}$

• connect pairs $(s_{ij},s_{kl})$ of split vertices with undirected edges and assign weights $\omega(s_{ij},s_{kl})$ according to:
  $\omega(s_{ij},s_{ji}) := w(e_{ij})$, i.e. the original edge weight
  $\omega(s_{ij},s_{jk}) := t(e_{ij},e_{jk})$, i.e. the transition cost
  $\omega(s_{ij},s_{kl}) := \infty$, otherwise

The optimal solution of the original problem can then be derived from the shortest path in the vertex-split graph by contracting edges resembling a transition between edges.

Answer 2

There is quite a bit of work on finding shortest paths with turn penalties. In a typical model, such as that used in the paper cited below, "Turn costs are stored in tables that are assigned to nodes." It may be (I am not certain) that this paradigm can be adapted to encode color-change penalties.

Geisberger, Robert, and Christian Vetter. "Efficient routing in road networks with turn costs." Experimental Algorithms. Springer Berlin Heidelberg, 2011. 100-111. (PDF download.)