亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

python dijkstra使用類實現算法可能出現的問題

python dijkstra使用類實現算法可能出現的問題

慕的地6264312 2023-09-19 17:27:38
所以我一直在嘗試用 python 創建一個圖形程序,其中包含 dfs、bfs 和 dijkstra 算法在其中實現的類,到目前為止已經提出:class Vertex:    def __init__(self, name):        self.name = name        self.connections = {}    def addNeighbour(self, neighbour, cost):        self.connections[neighbour] = costclass Graph:    def __init__(self):        self.vertexs = {}    def addVertex(self, newVertex):        new = Vertex(newVertex)        self.vertexs[newVertex] = new    def addEdge(self, src, dest, cost):        self.vertexs[src].addNeighbour(self.vertexs[dest], cost)    def dfs(self, start, end, visited):        visited[start] = True        print(start, end=' ')        if start == end:            # End node found            return True        else:            # Use depth first search            for connection in graph.vertexs[start].connections:                if visited[connection.name] == False:                    if self.dfs(connection.name, end, visited) == True:                        # Return true to stop extra nodes from being searched                        return True    def bfs(self, start, end, visited, queue):        if len(queue) == 0:            # Queue is empty            queue.append(start)        visited[start] = True        currentNode = queue.pop(0)        print(currentNode, end=' ')        if start == end:            # End node found            return True        else:            # Do breadth first search            for connection in graph.vertexs[currentNode].connections:                if visited[connection.name] == False:                    # Queue all its unvisited neighbours                    queue.append(connection.name)            for newNode in queue:                self.bfs(newNode, end, visited, queue)但我認為輸出似乎有問題。如果我想從節點 1 移動到節點 0,當前的輸出是:從節點 1 到節點 0 的 DFS 遍歷路徑: 1 6 2 0 從節點 1 到節點 0 的 BFS 遍歷路徑: 1 6 2 3 0 3 4 5 從節點 1 到 0 的最短可能路徑: 1 0 3 4 5 6 2 costing 10但是,我認為輸出應該是:從節點 1 到節點 0 的 DFS 遍歷路徑: 1 6 2 0 4 5 3 從節點 1 到節點 0 的 BFS 遍歷路徑: 1 6 2 3 0 4 5 從節點 1 到節點 0 的最短路徑: 1 6 2 0 costing 15任何人都可以看到這有什么問題嗎?
查看完整描述

1 回答

?
慕標5832272

TA貢獻1966條經驗 獲得超4個贊

您的代碼實際上存在幾個問題:

  1. 您需要指定您的 Djikstra 算法在哪里停止,在您的代碼中沒有提到什么是結束節點(在您的示例中它應該是 0)

  2. 計算成本并cost = result[len(result) - 1]不能獲得字典中的最后一個元素(字典通常沒有排序,因此“最后一個元素”甚至不存在!)。您應該將成本檢索為cost = result[end],其中end是最終節點,在您的示例中為 0。

  3. 您將該函數調用為result = graph.dijkstra(1, 0, graph.vertexs[2].connections, {}, {node: None for node in graphList}),但是,該函數的第三個參數應該是初始節點的鄰居集,所以它應該graph.vertexs[1].connections在您的情況下。

綜上所述,為了使代碼按預期工作,可以對函數進行如下修改:

def dijkstra(self, current, currentDistance, distances, visited, unvisited, end):

    for neighbour, distance in distances.items():

        if neighbour.name not in unvisited:

            continue

        newDistance = currentDistance + distance

        if unvisited[neighbour.name] is None or unvisited[neighbour.name] > newDistance:

            unvisited[neighbour.name] = newDistance

    visited[current] = currentDistance


    if current == end:

      return visited


    del unvisited[current]

    if not unvisited:

        return True

    candidates = [node for node in unvisited.items() if node[1]]

    current, currentDistance = sorted(candidates)[0]

    

    self.dijkstra(current, currentDistance, graph.vertexs[current].connections, visited, unvisited, end)

    return visited

并按如下方式調用它:


print("Shortest possible path from node 1 to 0:")

start = 1

end = 0

result = graph.dijkstra(start, 0, graph.vertexs[start].connections, {}, {node: None for node in graphList}, end)

cost = result[end]

path = " ".join([str(arrInt) for arrInt in list(result.keys())])

print(path, "costing", cost)

通過這樣做,輸出變為


從節點 1 到 0 的最短路徑: 1 6 2 0 成本 15


查看完整回答
反對 回復 2023-09-19
  • 1 回答
  • 0 關注
  • 113 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號