회원가입

[그래프] 33. Dijkstra 구현하기

NULL 2021-09-29
from collections import deque

class Node:
    def __init__(self, name):
        self.name = name
        self.adjustment = []
        self.completed = False
        self.distance = float("inf")
        self.predecessor = None

    def add_connection(self, node, weight):
        self.adjustment.append({"node": node, "weight": weight})
        node.adjustment.append({"node": self, "weight": weight})

    def backtracking(self):
        destination_node = self.predecessor

        shortest_path = f"{self.name}"

        while destination_node:
            shortest_path = f"{destination_node.name} - {shortest_path}"
            destination_node = destination_node.predecessor

        return f"도착지 [{self.name}] -> {shortest_path} : {self.distance} (shortest_distance)"

    def reset(self):
        self.completed = False
        self.distance = float("inf")
        self.predecessor = None

    def find_connected_nodes(self):
        queue = deque()

        queue.append(self)
        self.completed = True

        connection_nodes = []

        while queue:
            current_node = queue.popleft()

            for connection in current_node.adjustment:
                if not connection["node"].completed:
                    queue.append(connection["node"])
                    connection["node"].completed = True

            connection_nodes.append(current_node)

        for _node in connection_nodes:
            _node.reset()

        return connection_nodes

    def find_shortest_path(self, destination_node):
        first_node = self
        next_node = self

        # 시작지 Node 연결된 모든 경로 Node 찾기
        connected_node_set = first_node.find_connected_nodes()

        # 시작 Node 초기화
        if destination_node in connected_node_set:
            first_node.distance = 0

            print(f"출발지 [{first_node.name}]")

            # 모든 Node 가 completed 일 경우 끝난다.
            while next_node:
                for edge in next_node.adjustment:
                    if not edge["node"].completed:
                        # 엣지의 목적지 Node distance 가 더 크면 distance 를 바꾼다.
                        if edge["node"].distance > next_node.distance + edge["weight"]:
                            edge["node"].distance = next_node.distance + edge["weight"]
                            edge["node"].predecessor = next_node

                next_node.completed = True

                not_completed_node_set = list(filter(lambda x: not x.completed, connected_node_set))

                if not_completed_node_set:
                    not_completed_node_set.sort(key=lambda x: x.distance)
                    next_node = not_completed_node_set[0]
                else:
                    next_node = None

            print(destination_node.backtracking())

            # 끝날 때 초기화
            a_node.reset()
            b_node.reset()
            c_node.reset()
            d_node.reset()
            e_node.reset()
            return

        print("연결된 길이 없습니다.")

if __name__ == '__main__':
    # Create Nodes
    a_node = Node("A")
    b_node = Node("B")
    c_node = Node("C")
    d_node = Node("D")
    e_node = Node("E")

    # Create Edges
    a_node.add_connection(b_node, 2)
    a_node.add_connection(c_node, 3)
    b_node.add_connection(d_node, 4)
    b_node.add_connection(e_node, 5)
    c_node.add_connection(d_node, 1)
    d_node.add_connection(e_node, 2)

    # Run Dijkstra
    # Show path where destination distance is the shortest
    a_node.find_shortest_path(e_node)
    a_node.find_shortest_path(d_node)
    d_node.find_shortest_path(e_node)
0 0