Pseudo Code

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

dijkstra(n, edges, source):
   dist = [INF, INF, ...]; dist[source] = 0
   visited = all false
   repeat n times:
      u = unvisited vertex with smallest dist (none reachable -> stop)
      visited[u] = true
      for each edge (a -> b, weight w):
         if a == u and dist[u] + w < dist[b]:
            dist[b] = dist[u] + w
   replace every remaining INF with -1
   return dist

INF는 실제 거리보다 큰 숫자입니다 (예: 1000000000).
매 라운드마다 거리가 가장 짧은 방문하지 않은 정점을 선택하는 것이 다익스트라 알고리즘의 그리디(greedy) 핵심입니다. 완화(relax)를 위해 평면적인 간선 리스트를 스캔하는 방식은 코드를 단순하게 유지하며 모든 언어에서 작동합니다.

직접 해보기

이 레슨에는 코드 챌린지가 없습니다.

실력 점검

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

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

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