在使用集合的字典中删除给定节点时出现 KeyError，Dijkstra 最短路径算法

Question

如果我的代码中有任何未被注意到的错误，我深表歉意，我对 python 没有很好的经验，但是，整个周末一直在进行网络分配，并且对成功删除节点完全没有任何问题。

如果我能得到任何关于我哪里出错以及如何修复它的建议或解决方案，我将不胜感激。如果需要更多信息，我会尽我所能提供。我也愿意接受任何可能在代码的不同区域更有效的更改。

我应该完全删除一个节点，这实际上是宣布路由器已死并消除连接

问题区域：

class Graph():
    def __init__(self):
        self.graph_edges = []
        self.nodes = set()
        self.adjacency_list = {}

    def add_edge(self, frm, to, cost=0):
        self.graph_edges.append((frm, to, float(cost)))

        for edge in self.graph_edges:
            self.nodes.update([edge[0], edge[1]])

        self.adjacency_list = {node: set() for node in self.nodes}
        for edge in self.graph_edges:
            self.adjacency_list[edge[0]].add((edge[1], edge[2]))

    def remove_edge(self, node):
        if node in self.nodes:
            self.nodes.remove(node)
            #print(self.nodes)
        for nodeval in self.adjacency_list.copy():
            if node in self.adjacency_list:
                print(self.adjacency_list.values())
                del self.adjacency_list[node]
                #print(self.adjacency_list) 
        for check in self.graph_edges.copy():
            if node in list(check):
                self.graph_edges.remove(check)
                #print(ch)
        for k,v in self.adjacency_list.items(): # I'm assuming the problem is within here
            for a in v:
                if node == a[0]:
                    del self.adjacency_list[node]
                    #print(self.adjacency_list[node])

输出应该是这样的：

Start: a
End: f
Path: a->c->f
Cost: 11

#After removal of "c"
Start: a
End: f
Path: a->f
Cost: 14

我的完整代码在这里：

from collections import deque
import sys

INFINITY = float("inf")

class Router():
    def __init__(self, node, graph):
        self.node = node
        self.graph = graph

    def get_path(self, node):
        path, cost = self.find_path(self.node, node, self.graph)
        print("Start: {}".format(self.node))
        print("End: {}".format(node))
        print("Path: {}".format("->".join(path)))
        print("Cost: {}\n".format(int(cost)))

    def find_path(self, start, end, graph):
        unvisited = graph.nodes.copy()
        distance_from_start = {node: (0 if node == start else INFINITY) for node in graph.nodes}
        previous = {node: None for node in graph.nodes}

        while unvisited:
            current = min(unvisited, key=lambda node: distance_from_start[node])
            unvisited.remove(current)

            if distance_from_start[current] == INFINITY:
                break

            for nearest, distance in graph.adjacency_list[current]:
                new_path = distance_from_start[current] + distance
                if new_path < distance_from_start[nearest]:
                    distance_from_start[nearest] = new_path
                    previous[nearest] = current

            if current == end:
                break

        path = deque()
        current = end
        while previous[current] is not None:
            path.appendleft(current)
            current = previous[current]
        path.appendleft(start)

        return path, distance_from_start[end]
        
class Graph():
    def __init__(self):
        self.graph_edges = []
        self.nodes = set()
        self.adjacency_list = {}

    def add_edge(self, frm, to, cost=0):
        self.graph_edges.append((frm, to, float(cost)))

        for edge in self.graph_edges:
            self.nodes.update([edge[0], edge[1]])

        self.adjacency_list = {node: set() for node in self.nodes}
        for edge in self.graph_edges:
            self.adjacency_list[edge[0]].add((edge[1], edge[2]))

    def remove_edge(self, node):
        if node in self.nodes:
            self.nodes.remove(node)
            #print(self.nodes)
        for nodeval in self.adjacency_list.copy():
            if node in self.adjacency_list:
                print(self.adjacency_list.values())
                del self.adjacency_list[node]
                #print(self.adjacency_list) 
        for check in self.graph_edges.copy():
            if node in list(check):
                self.graph_edges.remove(check)
                #print(ch)
        for k,v in self.adjacency_list.items():
            for a in v:
                print(type(v))
                if node == a[0]:
                    del self.adjacency_list[node]
                    #print(self.adjacency_list[node])

if __name__ == "__main__":
    g = Graph()
    g2 = Graph()

    g.add_edge("a", "b", 7)
    g.add_edge("a", "c", 9)
    g.add_edge("a", "f", 14)
    g.add_edge("b", "c", 10)
    g.add_edge("b", "d", 15)
    g.add_edge("c", "d", 11)
    g.add_edge("c", "f", 2)
    g.add_edge("d", "e", 6)
    g.add_edge("e", "f", 9)

    g2.add_edge("x", "y", 7)
    g2.add_edge("x", "w", 9)
    g2.add_edge("x", "d", 14)
    g2.add_edge("y", "w", 10)
    g2.add_edge("y", "e", 15)
    g2.add_edge("w", "d", 11)
    g2.add_edge("w", "z", 2)
    g2.add_edge("d", "e", 6)
    g2.add_edge("e", "z", 9)

    router2 = Router("x", g2)
    router = Router("a", g)

    #print("Edges: {}\n".format(g.graph_edges))
    #print("Nodes: {}\n".format(g.nodes))
    #print("Adj List: {}\n".format(g.adjacency_list))
    router.get_path("f")
    #print(g.graph_edges)
    #print(g.adjacency_list)
    g.remove_edge("c")
    print(g.graph_edges)
    print(g.adjacency_list)
    print(g.nodes)
    #router.get_path("f")
    router2.get_path("e")
    node = "a"
    test = g.nodes.copy()
    adjtest = g.adjacency_list.copy()
    edgetest = g.graph_edges.copy()
    
    
    #if node in test:
        #test.remove(node)
        #print(test)
    #for nodeval in adjtest.copy().values():
        #if node in adjtest:
            #del adjtest[node]
            #print(adjtest)
    #for check in edgetest.copy():
        #if node in check:
            #edgetest.remove(check)
                #list_rem = list(check)
                #list_rem.clear()
                #check = tuple(list_rem)
            #print(check)
                #print(edgetest)
                #self.graph_edges.remove[node]

adjacency.list 图 g

{'c': {('d', 11.0), ('a', 9.0), ('f', 2.0)}, 'b': {('d', 15.0), ('c', 10.0)}, 'a': {('b', 7.0), ('c', 9.0), ('f', 14.0)}, 'f': set(), 'e': {('f', 9.0)}, 'd': {('e', 6.0)}}

Answer 1

我通过清除 graph_edges 以外的每个区域中的数据解决了这个问题，并删除了必要的值，然后我通过添加 graph_edges.[=11= 的数据重新创建了每个值]

这里是：

def remove_edge(self, node):
        for check in self.graph_edges.copy():
            if node in list(check):
                self.graph_edges.remove(check)

        self.nodes = set()
        self.adjacency_list = {}
        for edge in self.graph_edges:
            self.nodes.update([edge[0], edge[1]])

        self.adjacency_list = {node: set() for node in self.nodes}
        for edge in self.graph_edges:
            self.adjacency_list[edge[0]].add((edge[1], edge[2]))

在使用集合的字典中删除给定节点时出现 KeyError，Dijkstra 最短路径算法

KeyError when removing a given node within a dictionary that uses a set, Dijkstra Shortest Path Algorithim

python

dictionary

dijkstra

set

python-3.x