Doubt-_-'s blog

By Doubt-_-, history, 3 years ago, In English

If you are given a weighted and directed graph, which can have multi-edges between nodes. Each edge will have a color associated with it (let it be i). Find the shortest path between node A and node B, if there are multiples shortest paths, print the shortest path with the least number of colors in it. What can be the optimized solution for this?

Anything better than finding all shorted paths and then iterating thru each one and finding different colors for each, and printing the one with the least number of colors..?

If there's a similar question on the internet and someone can provide me a link for that, it would be really helpful.

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

If I understood correctly, even the unweighted version of the question you are asking is NP-hard. One can reduce the set cover problem to your problem quite easily:

Consider an arbitrary instance of a set cover problem:

Given $$$K$$$ subsets $$$S_1, S_2, ..., S_k \subseteq \lbrace 1, ..., n \rbrace$$$, choose as few as possible such that their union is $$$\lbrace 1, ..., n \rbrace$$$.

Let's create a graph with $$$n+1$$$ vertices, and add for each $$$i$$$ and each $$$x \in S_i$$$ the arc $$$(x, x+1)$$$ of color $$$i$$$. The path with the minimum number of colors between $$$1$$$ and $$$n+1$$$ corresponds to the solution of the set cover problem. It is known that set cover is NP-hard, therefore this problem is also NP-hard.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for a graph with weighted edges, simply exploring all the routes from node A to node B, and then for all the routes with min path sum, can't I check which path has the least number of colour switches? I do agree with your NP-hard explanation, but I was just confused why won't the brute force work in polynomial time..?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Consider a graph with $$$n + 1$$$ vertices and $$$2n$$$ edges, for each $$$i = 1..n$$$ there are two edges, that connect $$$i$$$ and $$$i + 1$$$. If you bruteforce all the paths from $$$1$$$ to $$$n + 1$$$, you will find $$$2^n$$$ paths, so the bruteforce would be exponentially slow.