I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum of the weights of the colors used. If we have for example a path A->B->C where A and C are red colored and B is blue colored, its length should count the weight of red only once (and the weight of the blue node)! I'm struggling to find an (efficient) algorithm that can do this. Dijkstra's algorithm or any greedy algorithm cannot work, because they require that a local optimum must be also a global optimum. Here, this is not the case because the weight of a vertex depends on the path to it. You could add vertecies for each combination of colors but this would add exponantially many vertecies.
It would be enough for me to find such an algorithm for DAGs.
Thank you very much for your help!