최단 경로 알고리즘의 이해

가중치가 있는 방향 그래프가 주어졌을 때, 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘을 구현해야 합니다. 그래프는 인접 리스트 형태로 주어지며, 각 엣지는 정수 가중치를 가집니다. 다음 중 이 문제를 해결하기 위해 적합한 알고리즘은 무엇인가요?

PYTHON

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v, weight):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append((v, weight))

    def shortest_path(self, start):
        # 구현할 알고리즘
        pass

답변

다익스트라 알고리즘 프림 알고리즘 벨만-포드 알고리즘 A* 알고리즘

로그인 후 제출하기