0

我得到了一项任务，我需要在我的 python 代码中应用 Dijkstra 的最短路径算法。假设我们涉及几个城市。我需要找到路线最短的那个。总之，任务是：

  • 找到最短的路线。
  • 列出所有可能的路径。

我成功地找到了城市中的最短路径，但我不知道如何使用 heapq 列出所有可能的路径。谁能帮我？

这是我为更好地理解图表而提供的图表：

我构建的图表

编码：

import heapq
from collections import defaultdict
global shortestPath
global shortestCost
shortestPath = "null"
shortestCost = 100000
def dijkstra(graph,src,dest): 
    h = []
  
    heapq.heappush(h,(0,src))
    global shortestPath
    global shortestCost
    global source
    while len(h)!=0:
        currcost,currvtx = heapq.heappop(h)
        if currvtx == dest:
            print("\t\t\t{} to {} with cost {}".format(src,dest,currcost))
            if currcost < shortestCost:
                if dest == src:
                    continue
                else:
                    shortestCost = currcost
                    shortestPath = dest
            break
        for neigh,neighcost in graph[currvtx]:
            heapq.heappush(h,(currcost+neighcost,neigh))

city = ["A","B","C","D","E","F"]
graph = defaultdict(list) 
graph["A"] = [("B",1),("C",5)]
graph["B"] = [('C', 6), ('D', 23)]
graph["C"] = [('E', 35)]
graph["D"] = [('F', 26)]
graph["E"] = [('D', 54)]

print ("\t=============================================================================")
print ("\t                     Dijkstra's Shortest Path Algorithm")
print ("\t=============================================================================")
print ("\n\tAssume 1 cost = 10 km")
print ("\n\tCity availability: {} ".format(city))
src = "A"
print ("\n\tPossible paths from {} :\n".format(src))
for i in city:
    dijkstra(graph,src,i)
print ("\n\t=============================================================================")
print("\t\tThe shortest path from {} is {} to {} with cost {}".format(src,src,shortestPath,shortestCost))
print ("\t=============================================================================")

输出：

    =============================================================================
                         Dijkstra's Shortest Path Algorithm
    =============================================================================

    Assume 1 cost = 10 km

    City availability: ['A', 'B', 'C', 'D', 'E', 'F'] 

    Possible paths from A :

            A to A with cost 0
            A to B with cost 1
            A to C with cost 5
            A to D with cost 24
            A to E with cost 40
            A to F with cost 50

    =============================================================================
        The shortest path from A is A to B with cost 1
    =============================================================================

如果这篇文章看起来不合适，我深表歉意，因为这是我在这里发布的第一个问题。

非常感谢您的帮助。谢谢你。

4

0 回答 0