小编Mac*_*iej的帖子

我有一个带有彩色加权边的有向图.有2种颜色.每个边缘只能有1种颜色.我想找到颜色变化有限的最短路径.从一个顶点可以出现最多2个边缘,其中有2种不同的颜色,2个边缘有2种不同的颜色.

例如,在此图中:

最短路径最多3个颜色变化将是9 最大0颜色变化最短路径6+1+4=11等.

我的解决方案是递归访问所有可能的路径并交换,如果递归找到一个更好的,使这个问题呈指数级.

是否存在针对此问题的非指数解决方案？