在彩色边缘图中找到最短的有效路径

3 回答

• 0

  复制你的图形，所以你有G1，G2，G3，你可以在每个图形中重定向紫边，如下所示：if（u1，v1）是G1中的紫边，然后将其改为（u1，v2） .

  即你有三个图表，每次你拿紫色边缘它会移动到下一个图形，而在G3上没有紫色边缘 . 该构造将紫色限制构建到结构中，然后将自动强制执行 .

  现在，您可以像往常一样找到从s到所有节点的最短路径 . 根据结果，您必须选择从s到u1，u2，u3的每条路径之间的更短 .

  总而言之，构造需要线性时间，并且新图形尺寸比原始尺寸大O（1）倍，因此APSP花费相同的时间，并且最终运行以确定找到的三条路径中的哪一条最短也是线性的 .

  回复于 2024-04-26T12:27:01+08:00
• 5

  每个顶点需要三条最短路径：0,1和2条紫色边缘的路径 . 在算法中，您需要在每个顶点存储三个不同的路径长度 . 当您考虑具有k个紫色边缘和边缘 t-u 的 s-t 路径时，如果边缘为绿色，则潜在的 s-t-u 路径具有k个紫色边缘，并且如果 s-t-u 路径比具有k个紫色边缘的其他 s-u 路径短，则存储其长度在顶点的槽k u . 或者，如果 t-u 边是紫色，则使用顶点 u 的槽k 1 . 你可以自己解决剩下的事吗？

  回复于 2024-04-26T12:27:01+08:00
• 1

  请注意，与您的 n 顶点相似的图形中没有循环的任何路径最长可达 n-1 .

  将长度 n 分配给每个紫色边，其中 n 是顶点数 . 找到从 S 到每个其他顶点的最短路径，例如，使用Dijkstra算法 .

  现在，检查路径长度：

  • 如果路径长度小于 n ，则只有绿色边缘的路径，因为即使一个紫色边缘也会增加路径长度超过 n-1 ;

  • 如果路径长度在 [n, 2n) 内，那么你只有一条紫色边缘，因为两条或更多条紫色边将增加路径长度超过 2n-1 ;

  • 如果路径长度在 [2n, 3n) 内，那么你只有两条紫色边，因为三条或更多条紫色边将增加路径长度超过 3n-1 ;

  • 否则不存在最多两条紫色边的路径 .

  回复于 2024-04-26T12:27:01+08:00