-2

I have a weighted undirected graph with N veritces and M edges. Each edge has its weight and colour. There are at most 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), weight of the shortest path is 12. I would like to design an algorithm that would solve this problem in considerable time (something like O(N) or O(N log N)), but I have no idea other than brute force.

I'm still looking for a solution. If someone knows how to solve it, please reply.

Constraints:

N <= 10^5

M <= 10^5

K <= 10^5

2

2 Answers 2

2

For every vertex, split it into 10 different vertices according to the color you take to reach it (the outgoing edges are the same for every copy). Note that this new graph is directed even if the original graph was undirected.

Then Dijkstra's algorithm in this new graph gives you the answer.

1

I'd say you could modify Dijkstra's Algorithm to do this. You'd just have to store an extra field for every vertex for last color passed so that when the algorithm requires the length of an edge you can add the color tax when the color of that edge is not equal to the last color passed. And then ofcourse you have to update that field. This would do it in O(M + N log N) time.

EDIT: With pseudocode:

 1 function Dijkstra(Graph, source):
 2     dist[source] ← 0
 3
 4     create vertex set Q
 5
 6     for each vertex v in Graph:           
 7         if v ≠ source
 8             dist[v] ← INFINITY
 9             prev[v] ← UNDEFINED
11         Q.add_with_priority(v, dist[v])
12
13     while Q is not empty:
14         u ← Q.extract_min()
15         for each neighbor v of u:
16             if color(prev[u], u) ≠ color(u, v)
17                 alt = dist[u] + length(u, v) + colorTax
18             else
19                 alt = dist[u] + length(u, v)
20             if alt < dist[v]
21                 dist[v] ← alt
22                 prev[v] ← u
23                 Q.decrease_priority(v, alt)
24
25     return dist[], prev[]

It turned out that with use of the prev-field a new field wasn't even needed.

6
  • That was my first idea, but I think it would eventually be exponential time algorithm. If I have a very large graph and from vertex 1 there are 100 edges to vertex 2 and from vertex 2 100 edges to vertex 3 etc. Apr 23, 2016 at 9:49
  • I added in some pseudocode, the alterations that I made shouldn't make any difference to the running time, which is proven to be O(M + N log N). About your worries about a graph where there are loads of edges between two vertices you could just calculate for which edge the length + optional colorTax is the lowest and then use that one. That shouldn't affect the running time too much. Unless you have enormous amounts of edges but if that is the case you won't get a good running time anyway. Apr 23, 2016 at 9:59
  • 1
    The pseudocode doesn't have a way of calculating which edge to pick if there are multiple edges yet as I explained in my last comment. So it doesn't output 12 or 15, its ambiguous between the two. As I mentioned, when you make a little calculation to find what edge is the smallest it would output 12. Apr 23, 2016 at 10:15
  • But from vertex 1 there are two edges, and if i choose the cheapest one, then I get the answer 15, because the algorithm will choose edge 1 -> 2 of weight 3 (+ 5 because of colour), and then go through 2 - > 3 (weight 2 and + 5 because of colour). Apr 23, 2016 at 11:35
  • Oh yeah sorry, didn't realize that. Maybe if the amount of colors is known and not too high you could create a distance field for every color that was used last to get there. And then just only see a node as completely done if that field is filled for every color that it has an incoming edge for. Is your graph directed or undirected by the way? Because for an undirected graph that might lead to problems where nodes are waiting for an edge that cant be reached without passing through the node itself. Apr 23, 2016 at 11:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.