Python：用最少路径数表示路径的图

Question

我已经实现了Dijkstra's Algorithm并修改了它。为了给定的图如果需要得到从A到F的最短路径

A --(R2,R4)-->M --(R2,R4)-->N --(R3)-->L --(R3)-->F

用修改过的代码或其他方式我感兴趣的是最少的路由数，所以在这种情况下作为有直接路由R1输出应该是

A --(R1)--> B --(R1)-->C --(R1)-->D --(R1)-->E--(R1)-->F

有人能建议我们怎么做吗。假设路线之间的距离相同。这是我的密码。 Fiddle Code for minimum routes

Answer 1

可以将多条边替换为一条权重边，权重为边数。
然后对其执行Dijkstra算法。在您的示例中，所需路径的图权重将为5，而未加权图上Dijkstra算法返回的路径将为6。你知道吗