はじめに
本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。
Mind（マインド）
プログラミング言語Mind（マインド）は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法1の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕４０周年となりました。
Mind（マインド）の入手方法
無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。
定番アルゴリズム：優先度付きキュー ダイクストラ法で使うための拡張とは
アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。
ここではその中のひとつ「ダイクストラ法で使うための拡張優先度付きキュー」を扱ってみます。「優先度付きキュー」（「優先度キュー」）は優先度の高い要素から順に取り出すデータ構造とロジックです。最小値を頂点とする木構造を構築しながら取り出しを行います。
最小値を頂点とする木構造を最小ヒープといいます。最小ヒープを使った場合の優先度とは値の小さいことを意味します。ノードの構築順（挿入順）に関わらず値の小さいノードから優先的に取り出すことができます。
シンプルな「優先度付きキュー」を扱った記事は下記を参照してください。
上記記事ではヒープを１次元配列で表現していましたが、本記事ではダイクストラ法で使用するため、ヒープを頂点番号と距離からなる構造体の配列として扱います。
また、本記事ではダイクストラ法で使用するための「キー減少」を対応します。
優先度付きキュー（最小ヒープ）を使わないシンプルな「ダイクストラ法」を扱った記事は下記を参照してください。
お題のソースコード
最初に下図のようなツリー構造を構築します。値は距離を意味します。すべての子 ≥ 親 を満たしていることがポイントです。
1
/ \
3 10
/
5
この二分木構造を１次元配列の数列で表すと下記のようになります。基本的このような二分木構造を使って、小さい値から値を取り出すことにお題は変わりありません。
1，3，10，5
ツリー構造への挿入順は下記の想定です。小さい順に挿入していないことがポイントです。
5 → 3 → 10 → 1
上記の単純な１次元配列の場合は、配列のインデックスが頂点番号を意味していました。
しかし、ダイクストラ法では
・どの頂点の距離が更新されたのか
・どの頂点を次に取り出すべきか
を管理する必要がありますので、ヒープの再構築によっても変化しない頂点番号を保持します。基本的には距離と頂点番号の構造体の配列とした方が素直な実装となります。
頂点番号も１次元配列で追加して、距離の１次元配列のインデックスと同期して操作することもできますが、やや煩雑となります。
本記事では下記のような構造体を定義します。
ヒープは 距離と 頂点番号
前記ツリー図に頂点番号をかっこ書きで付記すると下図のようになります。カッコ内のvは頂点vertexの意です。
1 (v4)
/ \
3 (v2) 10 (v3)
/
5 (v1)
ヒープ構造体の配列は下記の状態を意味します。頂点番号の値のvは頂点vertexの意です。実際にはvを除いたただの数字が入ります。
ヒープ[1] = (1, v4)
ヒープ[2] = (3, v2)
ヒープ[3] = (10, v3)
ヒープ[4] = (5, v1)
Mindの配列の基数は１です。基数０の配列を使った一般的なプログラミング言語の実装とはインデックスの扱いが異なる点にご留意ください。また、上記の疑似言語表現では一般的なプログラミング言語の配列表現でかぎカッコを使っていますが、Mindの場合はかっこ()表記となります。
下記がソースコード全文となります。今回はダイクストラ法の実装で利用するため、ライブラリとして定義して、テスト用のメイン部分を別ソースとしました。
ライブラリ
最大容量は 数値 １００。
ヒープサイズは 変数。
インデックス位置は 最大容量の 変数。
ヒープ型は 型紙
距離＿は 変数
頂点番号＿は 変数
全体は 距離＿と 頂点番号＿。
ノードは 構造体
距離は 変数
頂点番号は 変数
ヒープは 距離と 頂点番号
全体は 最大容量の ヒープ。
ヒープを初期化するとは （・ → ・）
ヒープサイズを クリアし
最大容量で 回数指定し
インデックス位置（回数）に －１を 入れ
繰り返すこと。
ヒープ入替するとは （インデックス左 インデックス右 → ・）
インデックス左は 変数
インデックス右は 変数
一時ヒープは 構造体 ヒープ型
インデックス右に 入れ
インデックス左に 入れ
一時ヒープに ヒープ（インデックス左）を 入れ
ヒープ（インデックス左）に ヒープ（インデックス右）を 入れ
ヒープ（インデックス右）に 一時ヒープを 入れること。
上方へヒープ構築するとは （インデックス → ・）
インデックスは 変数
親のインデックスは 変数
インデックスに 入れ
インデックスが １に 等しい ならば 終わり つぎに
インデックスを ２で 割って 親のインデックスに 入れ
距離（親のインデックス）が 距離（インデックス）より 大きい
ならば
親のインデックスと インデックスを ヒープ入替し
親のインデックスで 上方へヒープ構築する
つぎに。
下方へヒープ構築するとは （インデックス → ・）
インデックスは 変数
インデックス左は 変数
インデックス右は 変数
インデックス最小値は 変数
インデックスに 入れ
インデックスに ２を 掛けて インデックス左に 入れ
インデックス左に １を 加えて インデックス右に 入れ
インデックス左が ヒープサイズより 大きい ならば 終わり つぎに
インデックス最小値に インデックス左を 入れ
インデックス右が ヒープサイズ 以下
ならば
距離（インデックス右）が 距離（インデックス左）より 小さい
ならば
インデックス最小値に インデックス右を 入れ
つぎに
つぎに
距離（インデックス）が 距離（インデックス最小値） 以下
でなければ
インデックスと インデックス最小値で ヒープ入替し
インデックス最小値で 下方へヒープ構築する
つぎに。
ヒープへ挿入するとは （ヒープ型挿入値 → ・）
一時ヒープは 構造体 ヒープ型
一時ヒープに 入れ
ヒープサイズが 最大容量 以上
ならば 重大エラー
つぎに
ヒープサイズを 一つ増加し
一時ヒープを ヒープ（ヒープサイズ）に 入れ
ヒープサイズで 上方へヒープ構築すること。
ヒープから最小値を取り出すとは （・ → ヒープ型最小値）
最小値は 構造体 ヒープ型
ヒープサイズが ０に 等しい
ならば 重大エラー
つぎに
最小値に ヒープ（１）を 入れ
ヒープ（１）に ヒープ（ヒープサイズ）を 入れ
ヒープサイズを 一つ減少し
１で 下方へヒープ構築し
最小値を 返すこと。
ヒープから最小値を参照するとは （・ → ヒープ型最小値）
ヒープサイズが ０に 等しい
ならば 重大エラー
つぎに
ヒープ（１）を 返すこと。
キーの削減とは （頂点番号キー 新しい距離 → ・）
頂点番号キーは 変数
新しい距離は 変数
一時インデックスは 変数
新しい距離に 入れ
頂点番号キーに 入れ
一時インデックスに インデックス位置（頂点番号キー）を 入れ
距離（一時インデックス）に 新しい距離を 入れ
一時インデックスで 上方へヒープ構築すること。
ヒープに含まれる？とは （頂点番号キー → 真偽）
頂点番号キーは 変数
頂点番号キーに 入れ
インデックス位置（頂点番号キー）が -1と 異なる？。
ヒープ状態を表示するとは （・ → ・）
ヒープサイズで 回数指定して
ノードの 頂点番号（回数）を 数値表示し 「，」を 表示し
繰り返す
改行し
ヒープサイズで 回数指定して
ノードの 距離（回数）を 数値表示し 「，」を 表示し
繰り返す
改行すること。
ノードに値をセットするとは （頂点番号 距離 親の構造体情報 → ・）
親のノードは 構造体情報
親のノードに 入れ
親のノードの 距離＿に 入れ
親のノードの 頂点番号＿に 入れること。
ノードの値を数値表示するとは （親の構造体情報 → ・）
親のノードは 構造体情報
親のノードに 入れ
親のノードの 距離＿を 数値表示し 改行し
親のノードの 頂点番号＿を 数値表示し 改行すること。
「ヒープへ挿入」「ヒープから最小値を取り出す」「ヒープから最小値を参照する」はヒープ型構造体を扱うように拡張されています。
「ヒープへ挿入」の際は頂点番号の重複をチェックしてはじいた方がよい気がしますが、これを書いていたときは考えが及んでいないので処理単語内部でのチェックは割愛されています。ただし「ヒープに含まれる？」が実装されていますので、「ヒープへ挿入」する前に頂点番号をチェックすることはできます。
内部的に使っている「下方へヒープ構築する」「上方へヒープ構築する」という処理単語は再帰的に書かれています。
ヒープ構造体の配列の「最大容量」はお題の数列の定数配列の要素数より大きめに確保してあります。
テスト実行用メインプログラム
"pq4dijkstra"を コンパイルする。
メインとは （・ → ・）
挿入値は 構造体 ヒープ型
参照値は 構造体 ヒープ型
ヒープを初期化し
１と ５と 挿入値で ノードに値をセットし
挿入値を ヒープへ挿入し
２と ３と 挿入値で ノードに値をセットし
挿入値を ヒープへ挿入し
３と １０と 挿入値で ノードに値をセットし
挿入値を ヒープへ挿入し
４と １と 挿入値で ノードに値をセットし
挿入値を ヒープへ挿入し
ヒープ状態を表示する
ヒープから最小値を参照し 参照値に 入れ
参照値で ノードの値を数値表示し
ヒープ状態を表示する
３で 回数指定し
ヒープから最小値を取り出し 参照値に 入れ
参照値で ノードの値を数値表示し
ヒープ状態を表示する
繰り返すこと。
「ヒープへ挿入」という処理単語を数回実行することで最小ヒープを構築しています。値の挿入順は小さい順ではないことがポイントです。ただし、ダイクストラ法拡張では挿入時に頂点番号を指定しておきます。
「ヒープから最小値を取り出す」という処理単語を３回繰り返すことで距離が小さい値のヒープ構造体を取り出しています。取り出しによってヒープ構造体配列の要素数は減っていきます。
お題のソースコードをコンパイル
では、コンパイルしてみます。Mind8によるコンパイル結果です。
C:\developments\vscode\mind9\algorithm>mind pq4dijkstratest file
日本語プログラミング言語 Ｍｉｎｄ Version 8.07 for Windows
Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> pq4dijkstratest.exe
実行結果
実行結果です。
C:\developments\vscode\mind9\algorithm>pq4dijkstratest
4，2，3，1，
1，3，10，5，
1
4
4，2，3，1，
1，3，10，5，
1
4
2，1，3，
3，5，10，
3
2
1，3，
5，10，
5
1
3，
10，
相当かなり芸のない出力ですが、小さい値から取り出されていることがわかります（？）
下記の１行目の数列は挿入時に指定した頂点番号です。２行目の数列が距離です。
4，2，3，1，
1，3，10，5，
最初の上記出力はヒープ構築直後のもので、次の同じ出力は「ヒープから最小値を参照」した直後のものです。参照するはヒープを再構築しないので同じ値となります。
下記の出力は「ヒープから最小値を参照」または「ヒープから最小値を取り出」したヒープ構造体の値で、１行目は頂点番号、２行目が距離を意味します。
1
4
「ヒープから最小値を取り出」した後は構造体の要素数が減っていることがわかります。頂点番号と距離のペアは維持したまま、配列のインデックスが変化します。
2，1，3，
3，5，10，
おわりに
いかがでしたでしょうか？わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。
-
演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法（ポーランド記法）+ 1 2、後に記述する後置記法（逆ポーランド記法）1 2 +がある。日本語は１と ２を 足す。 ↩