Pseudo Code

Coddyの「ダイクストラ法 - グラフアルゴリズム」コースのレッスン 4/9。

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）です。
各ラウンドで最短距離の未訪問の頂点を選択することが、ダイクストラ法の強欲法（グリーディ）としての核心です。フラットなエッジリストをスキャンして緩和（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