벨만포드 알고리즘

주석 있는 코드 

def solution(graph, source):
    # 1. 그래프의 노드 수
    num_vertices = len(graph)
    # 2. 거리 배열 초기화 
    distance = [float("inf")] * num_vertices
    distance [source] = 0
    # 3. 직전 경로 배열 초기화 
    predecessor = [None] * num_vertices

    # 4. 간선 수 만큼 반복하여 최단 경로 갱신
    for temp in range(num_vertices - 1):
        for u in range(num_vertices):
            for v, weight in graph[u]:
                # 5. 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 저장된 노드 v까지의
                # 거리보다 짧은 경우
                if distance[u] + weight < distance[v]:
                    # 6. 최단 거리를 갱신해줌.
                    distance[v] = distance[u] + weight
                    # 7. 직전 경로를 업데이트해줌.
                    predecessor[v] = u

    # 8. 음의 가중치 순회 체크 
    for u in range(num_vertices):
        for v, weight in graph[u]:
            # 9. 현재 노드 u를 거쳐서 노드 v로 가는 경로의 거리가 기존에 
            # 저장된 노드 v까지의 거리보다 짧은 경우
            if distance[u] + weight < distance[v]:
                # 10. 음의 가중치 순회가 발견됐음, [-1] 반환
                return [-1]

    return [distance, predecessor]

 

 

주석 간소화 코드

def solution(graph, source):
    vLen = len(graph)
    distances = [float("inf")] * vLen
    distances[source] = 0 # 최단거리 리스트, 시작은 0
    predecessor = [None] * vLen # 직전 노드 
    print("")

    # 일단 최단거리 그거 구해야함. 
    for i in range(0, vLen-1): # n-1번 반복함
        for v, node in enumerate(graph):
            for oneNode in node:
                currNode, weight = oneNode
                distance = distances[v] + weight
                if distance < distances[currNode]:
                    distances[currNode] = distance
                    predecessor[currNode] = v

    # 음의 순환 잡기 
    for v, node in enumerate(graph):
        for oneNode in node:
            currNode, weight = oneNode       
            distance = distances[v] + weight
            if distance < distances[currNode]:
                return [-1]

    return [distances, predecessor]