python dijkstra

Dijkstra.py

class Dijkstra:
    # 초기화
    # S는 방문한 노드가 아직 없으므로 공집합 상태이다.    
    # D는 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
    # Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
    S = set()
    d = {}
    Q = set()

    @classmethod
    def find_shortest_path(cls, graph, source):
        for node in graph.nodes:
            cls.Q.add(node)
            cls.d[node] = 0 if node == source else float('inf')

        cls.calc_neighbor_distance(graph, source)
        
        return cls.d

    # 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.
    @classmethod
    def calc_neighbor_distance(cls, graph, source):
        neighbor = []

        # 이웃 노드를 방문하고 거리를 계산한다.
        for start, end_list in graph.edges.items():
            for end, distance in end_list:
                if start == source:
                    sum = cls.d[source] + distance
                    if cls.d[end] == float('inf'): # 첫 방문일 경우에는 값을 갱신한다.
                        cls.d[end] = sum
                    elif cls.d[end] > sum: # 첫 방문이 아닐 경우에는 최소 경로일 경우에만 값을 갱신한다.
                        cls.d[end] = sum
                    neighbor.append(end) # 이웃 노드는 임시 큐에 저장하여 보관한다.

        # 완료된 노드는 집합 Q 에서 제거하고 집합 S 에 추가한다.
        cls.Q.remove(source)
        cls.S.add(source)

        # 이웃 노드에서 동일한 작업을 반복한다.
        for node in neighbor:
            if node not in cls.S: 
                cls.calc_neighbor_distance(graph, node)

DirectedGraph.py

class DirectedGraph:
    def __init__(self):
        self.nodes = set()
        self.edges = {}

    def add_node(self, node):
        self.nodes.add(node)

    def add_edge(self, start, end, distance):
        if start in self.nodes and end in self.nodes:
            if start in self.edges:
                self.edges[start].append((end, distance))
            else:
                self.edges[start] = [(end, distance)]
        else:
            print("노드가 존재하지 않습니다.")

    def __str__(self):
        result = "노드: {}\n엣지: ".format(self.nodes)
        for start, end_list in self.edges.items():
            for end, distance in end_list:
                result += "({}, {}, {}) ".format(start, end, distance)
        return result

main.py

from DirectedGraph import DirectedGraph
from Dijkstra import Dijkstra

# 방향 그래프 생성
graph = DirectedGraph()

# 노드 추가
graph.add_node("A")
graph.add_node("B")
graph.add_node("C")
graph.add_node("D")
graph.add_node("E")
graph.add_node("F")

# 엣지 추가
graph.add_edge("A", "B", 10)
graph.add_edge("A", "C", 30)
graph.add_edge("A", "D", 15)
graph.add_edge("B", "E", 20)
graph.add_edge("C", "F", 5)
graph.add_edge("D", "C", 5)
graph.add_edge("D", "F", 20)
graph.add_edge("E", "F", 20)
graph.add_edge("F", "D", 20)

# 그래프 출력
print(graph)

# Dijkstra 알고리즘 결과 출력
print(Dijkstra.find_shortest_path(graph, "A"))

# 출력값
# 노드: {'C', 'A', 'F', 'D', 'E', 'B'}
# 엣지: (A, B, 10) (A, C, 30) (A, D, 15) (B, E, 20) (C, F, 5) (D, C, 5) (D, F, 20) (E, F, 20) (F, D, 20)
# {'C': 20, 'B': 10, 'F': 25, 'D': 15, 'E': 30, 'A': 0}