파이썬 자료구조 알고리즘(python data structure) 벨만포드로 풀어주세요 ㅠㅠㅠ

[kaypop123]

(1) 입력:

• 정점의 수 (V)와 간선의 수 (E)가 첫 줄에 주어진다..
• 다음 줄에는 각 간선의 정보를 나타내는 세 개의 정수 u, v, w가 주어진다. 이는 정점 u에서 정점 v로의 가중치 w 간선을 나타낸다.
• 마지막으로 시작 정점 source가 주어진다.
  예시 :
  5 8
  0 1 -1
  0 2 4
  1 2 3
  1 3 2
  1 4 2
  3 2 5
  3 1 1
  4 3 -3
  0

(2) 출력: 시작 노드에서 각 노드로의 최단 거리를 출력한다.

• 시작 노드에서 각 노드로의 최단 거리 경로를 출력한다. 경로는 시작 노드에서 목표 노드까지의 노드 순서를 나타내야 한다.
  예시 :

Shortest distances from source(0):
0 0 2 -1 -3
Shortest paths:
0 to 0: 0
0 to 1: 0 -> 1
0 to 2: 0 -> 1 -> 2
0 to 3: 0 -> 1 -> 3
0 to 4: 0 -> 1 -> 3 -> 4

(3) if name = “main”:에서 테스트을 수행한다.

[minkyu97]

def bellman_ford(edges, n_vertex, start):
    """
    edges[n] -> (orig, dest, weight): n번째 간선. orig에서 dest로 거리는 weight
    n_vertex: 정점의 수
    start: 시작 정점 번호 x
    
    distance_table[n] -> x: 시작점부터 정점 n까지의 최단 거리 x
    parent_table[n] -> x: 시작점부터 정점 n까지의 최단 경로 중, 정점n 오기 직전에 지난 정점 번호 x
    """
    distance_table = [float("inf")] * n_vertex
    parent_table = [None] * n_vertex
    distance_table[start] = 0

    # 모든 간선에 대해서 업데이트
    def iter():
        for orig, dest, weight in edges:
            old_path_distance = distance_table[dest]
            new_path_distance = distance_table[orig] + weight
            if old_path_distance > new_path_distance:
                distance_table[dest] = new_path_distance
                parent_table[dest] = orig

    # iter()을 정점의 수만큼 반복
    for _ in range(n_vertex):
        iter()

    # 음의 싸이클에 포함된 정점들을 탐지
    for orig, dest, weight in edges:
        old_path_distance = distance_table[dest]
        new_path_distance = distance_table[orig] + weight
        if old_path_distance > new_path_distance:
            distance_table[dest] = float("-inf")
            parent_table[dest] = None

    print(distance_table)
    print(parent_table)

주어진 예시에서 0 0 2 -1 -3 이게 답인가요?..
전 0 -1 2 -2 1 일케 나오네요 ㅠ 틀렸을 수도

[joongwon]

챗지피티가 잘 풀어줘요