Implementation (Part 1)

Coddy의 벨만-포드 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 5번째.

먼저, 모든 간선에 대해 한 번의 완화(relaxation) 과정을 수행합니다.

챌린지

중급

벨만-포드(Bellman-Ford)는 단 하나의 연산을 반복하는 것입니다. 바로 모든 간선에 대한 경로 완화(relaxation pass)입니다. 이제 단일 패스를 구현해 봅시다.

n, 평면 구조의 edges 배열(세 개씩 짝을 이루는 유향 간선, 가중치는 음수일 수 있음), 그리고 source를 인자로 받는 relaxAll이라는 함수를 작성하세요. dist[source] = 0으로 시작하고 나머지는 모두 무한대로 설정한 뒤, 모든 간선을 한 번씩(주어진 순서대로) 완화하고 결과 거리 배열을 반환하세요. 아직 도달하지 못한 정점의 거리는 -1로 표시합니다.

단 한 번의 패스만 수행하기 때문에, 여러 간선을 거쳐야만 도달할 수 있는 정점들은 여전히 -1일 수 있습니다. 이는 의도된 결과입니다.

직접 해보기

#include <stdlib.h>

int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
    // 여기에 코드를 작성하십시오
    *returnSize = 0;
    return edges;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

벨만-포드 알고리즘 - 그래프 알고리즘의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2