Implementation (Part 2)

Coddy의 다익스트라 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 6번째.

이제 그리디 최단 경로 계산입니다.

챌린지

중급

이제 전체 알고리즘을 구현해 보세요.

n, 평탄화된 edges 배열(트리플 구조, 유향, 음수가 아닌 가중치), 그리고 source를 인자로 받는 dijkstra라는 이름의 함수를 작성하세요. 이 함수는 source에서 각 정점 v까지의 최단 거리를 담은 배열을 반환해야 합니다. 도달할 수 없는 정점의 거리는 -1로 표시하세요.

시작할 때 source의 거리는 0으로, 나머지 모든 정점의 거리는 아주 큰 값인 "무한대(infinity)"로 설정하세요. 그런 다음, n번 반복하며 방문하지 않은 정점 중 가장 가까운 정점을 확정하고, 해당 정점에서 나가는 간선들을 완화(relax)하세요.

직접 해보기

#include <stdlib.h>

int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
    // 여기에 코드를 작성하세요
    *returnSize = 0;
    return edges;
}

실력 점검

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

다익스트라 알고리즘 - 그래프 알고리즘의 모든 레슨

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) 프로젝트 레슨

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2