基于条件语句的有向图中的最小跳数

Question

有向图G由顶点V和边线E给出，分别代表火车站和单向火车路线。

不同编号的火车在一对顶点之间在一个方向上移动。

[[G的顶点通过具有分配的火车编号的火车相互连接。

跳数是当乘客需要在穿越曲线图的同时换火车时定义的。旅客仅在车号发生变化时才需要换车。

给出两个顶点

V1

和V2，如何计算从V1开始达到V2所需的最小跳数？

---

在上面的示例中，顶点

0

和3之间的最小跳数为1。[从0到3，有两条路径，这是

0 -> 1 -> 2 -> 7-> 3

Hop Count 4

跳数为4，因为乘客必须从火车A换乘B，然后再换乘C和B。

和

0 -> 5 -> 6 -> 8 -> 7 -> 3

Hop Count 1

跃点数为1，因为乘客仅需要一条火车路线，B即可从顶点

0

到3因此最小跳数为1。

---

输入示例

输入图创建

待解决的输入

---

输出示例

输出-用跳数解决

Hop Count列中的0表示无法到达目的地

Answer 1

假设不同的trainID的数量相对较小（例如您的示例中为4），那么我建议使用分层图方法。

顶点的数量为N，边的数量为M，不同的trainID的数量为K。让我们将图划分为K个图。 （graphA，graphB，...）graphA仅包含标有A的边，依此类推。每个图形中每个边缘的权重为0。现在在这些图形之间创建边。图之间的边缘代表“跳数”grapha [i]连接到graphB [i]，graphC [i]，...每个边的权重为1。现在，对于每个运行的图，Dijkstra从该图中的V1开始的最短路径算法，并从所有图中的V2读取结果，都取最小值。这样，为每个图运行dijkstra的结果的最小数就是您的最小跳数。内存复杂度为O(K*(N+M))时间复杂度为O(K*(((2^K)*N+M)*log(KV)))（2 ^ K）* N来自以下事实：对于每1 <= i <= N，顶点graphA [i]，graphB [i]，...必须彼此连接，这为2 ^ K个连接每个i，总共（2 ^ K）* N个连接。

对于K相对较小（例如您的示例中为4，但N和M很大的情况，此算法的工作原理就像一个魅力。不过，它不适合K大的情况。

我不确定是否清楚。告诉我是否需要更详细的说明。

编辑：希望这使我的算法更加清晰。黑色边缘的权重为0，红色边缘的权重为1。通过使用分层图方法，我们将特殊的图转换为纯加权图，因此我们可以在其上运行Dijkstra的算法。对不起，图片难看。