实际上，我已经考虑这个分配的问题有一段时间了，但我无处可去……我知道 Bellman-Ford、Dijkstra 和 Floyd Warshall。
几乎这是一个标准的最短路径问题，有 V 个顶点和 E 个边，每个边的长度为 L，颜色为 C。它们是双向的。
唯一的限制是您应该找到最短路径的长度，而不要使用相同颜色的 2 个连续边。
如果 V 较小，Floyd-warshall 可以工作，但 V 以 (3, 50000) 为界。
有什么帮助吗？想法？
问问题
406 次
2 回答
1
尝试类似 Dijkstra 的方法，但要跟踪到每个顶点以特定颜色结束的最短路径。
于 2012-10-10T03:41:17.687 回答
0
http://paginas.matem.unam.mx/publicaciones/phocadownloadpap/Preliminares-DF/879.pdf上的论文，弧色有向图中的最短 H 限制路径，似乎使用了一种非常标准的寻路算法，但是为每个顶点的每种颜色保留单独的信息。它适用于有向图，但我想您可以从无向图构造有向图。
于 2012-10-10T04:22:11.167 回答