python : Graph suggesting path with minimum number of paths

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

您可以修改图形，以便从路线上的每个早期顶点到后面的顶点都有一条边(更改链接代码中的第 49-51 行):

for route,path in routes.iteritems():
    for i in range(len( path)-1):
        for j in range(i, len(path)):
            data.append( (path[i] , path[j] , 1 , route)) 

输出:

For  A to F  : > 
(('A', 'F'), ['R1'])

如果您想扩展返回的路线，您可以将打印代码修改为:

print "For  A to F  : > "
for (s,d),r in  find_shortest_path("A","F"):
    b = False
    for i in range(len(routes[r[0]])):
        v = routes[r[0]][i]
        if v == s:
            b = True
        elif v == d:
            break
        if b:
           print((v, routes[r[0]][i+1]), r)

输出:

For  A to F  : > 
(('A', 'B'), ['R1'])
(('B', 'C'), ['R1'])
(('C', 'D'), ['R1'])
(('D', 'E'), ['R1'])
(('E', 'F'), ['R1'])