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

2024-03-28 21:40:38 发布

您现在位置:Python中文网/ 问答频道 /正文

Image for describing the test case of problem statement

我已经实现了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


Tags: 代码路径距离路由方式情况路线algorithm
2条回答

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

您可以修改图形,使路线上的每个早期顶点都有一条边到后面的顶点(更改链接代码中的第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'])

相关问题 更多 >