最初に「あい」を学ぶことば日本語でプログラミング入門（Mindで定番アルゴリズム： ダイクストラ法）

はじめに

本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。

Mind（マインド）

プログラミング言語Mind（マインド）は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法¹の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕４０周年となりました。

Mind（マインド）の入手方法

無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。

定番アルゴリズム：ダイクストラ法とは

アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。

ここではその中のひとつ「ダイクストラ法」を扱ってみます。「ダイクストラ法」はある頂点から他のすべての頂点への最短距離と経路を求めるためのロジックです。今回は優先度付きキューというヒープを使ったロジックは使わず、シンプルな状態を考察します。

お題のソースコード

今回は下記のような経路を想定します。数字は頂点の番号で４つの頂点があるとします。かっこ値は頂点間の距離を意味します。

 1 －(4)－> 2 －(1)－> 4
  \       
  (1)      
    \     
     > 3 －(2)－> 2
        \
          (5)
             \
              > 4

上記のグラフの頂点間の関係を分割すると下記のようになります。

4頂点 1,2,3,4 かっこ値は頂点間の距離
 1→2(4), 1→3(1)
 2→4(1)
 3→2(2), 3→4(5)

Mindの配列の添え字の基数は１から始まりますので、下記のような２次元配列で上記の経路を記述します。

dijkstra.src

※                               頂点１　２　３　４
頂点１の各頂点までの距離は　定数配列    ０, 4,  1,  ∞。
頂点２の各頂点までの距離は　定数配列    ∞, ０,  ∞,  1。
頂点３の各頂点までの距離は　定数配列    ∞,  2, ０,  5。
頂点４の各頂点までの距離は　定数配列    ∞,  ∞,  ∞, ０。

∞は経路の距離に対して十分大きな無限大と言える値です。今回は１０億としています。

dijkstra.src

∞は　               定数　１０００００００００。 （１０億）

Mindの場合、２次元配列は構造体で表現されます。前記の各１次元定数配列で４つの頂点のそれぞれ各頂点への距離を初期化します。

dijkstra.src

出発頂点数最大は　  定数　４頂点。

グラフを初期化するとは （・　→　・）
    出発頂点数最大で　回数指定し
        出発頂点（回数）に　回数を　入れ
    繰り返す
    頂点距離群（１）に　頂点１の各頂点までの距離を　入れ
    頂点距離群（２）に　頂点２の各頂点までの距離を　入れ
    頂点距離群（３）に　頂点３の各頂点までの距離を　入れ
    頂点距離群（４）に　頂点４の各頂点までの距離を　入れる。

４つの頂点の最小距離候補の１次元配列を∞で初期化します。

dijkstra.src

距離は　出発頂点数最大の　変数。

ダイクストラ法で最短経路を求めるとは （・　→　・）
        確定判定は   出発頂点数最大の　バイト変数
          ※～略～

    出発頂点数最大で　回数指定し
        距離（回数）に　∞を　入れ
        確定判定（回数）を　クリアし　※０を　入れ
    繰り返す
    距離（１）を　クリアし　※０を　入れ
          ※～略～

続いて、下記のように大枠頂点数でループします。その中に頂点数のループを２つ入れ子で保持する構造となります。

dijkstra.src

    出発頂点数最大で　回数指定し

        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定し
          ※～略～
          頂点Noを　一つ増加し
        繰り返す
          ※～略～

        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定し
          ※～略～
          頂点Noを　一つ増加し
        繰り返す

    繰り返す。

入れ子の最初のループでは、距離候補が最小の頂点Noを探し暫定値とします。

dijkstra.src

          ※～略～

        最小距離候補に　∞を　入れ
        最小距離候補の頂点Noに　最短頂点未確定を　入れ
        
        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定し
            確定判定（頂点No）が　偽？　かつ　
                    距離（頂点No）が　最小距離候補より　小さい
            ならば
                最小距離候補に　距離（頂点No）を　入れ
                最小距離候補の頂点Noに　頂点Noを　入れ
            つぎに
            頂点Noを　一つ増加し
        繰り返す
          ※～略～

後半の入れ子のループでは、暫定値の最小距離候補の頂点から次の頂点までの距離を加算し、最小距離候補より小さければその値で最小距離候補を更新して確定していきます。

dijkstra.src

        確定判定（最小距離候補の頂点No）を　セットし　※１を　入れ

        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定
            頂点距離（最小距離候補の頂点No、頂点No）が　∞に　等しい
            でなければ
                距離（最小距離候補の頂点No）に　頂点距離（最小距離候補の頂点No、頂点No）を　加えて　複写し
              　距離（頂点No）より　小さい
                ならば
                　距離（頂点No）に　入れ
                さもなければ
                　捨て　※入れない場合は捨てる
                つぎに
            つぎに
            頂点Noを　一つ増加
        繰り返す

後半のループ内では「複写」を使って、加算値の比較と代入を行う中間変数の定義を節約してみました。

下記がソースコード全文となります。

dijkstra.src

∞は　               定数　１０００００００００。 （１０億）
出発頂点数最大は　  定数　４頂点。
到達頂点数最大は　  定数　４頂点。
最短頂点未確定は　　定数　－１。

グラフは　構造体
        出発頂点は　変数
            頂点距離は　変数
        頂点距離群は　到達頂点数最大の　頂点距離
    各頂点距離は　出発頂点と　頂点距離群　　
全体は　出発頂点数最大の　各頂点距離。

距離は　出発頂点数最大の　変数。

※ 隣接行列（4頂点 1,2,3,4 かっこ値は頂点間の距離）
※ 1→2(4), 1→3(1)
※ 2→4(1)
※ 3→2(2), 3→4(5)

※ 1 －(4)－> 2 －(1)－> 4
※  \       
※  (1)      
※    \     
※     > 3 －(2)－> 2
※           \
※           (5)
※             \
※              > 4

※                               頂点１　２　３　４
頂点１の各頂点までの距離は　定数配列    ０, 4,  1,  ∞。
頂点２の各頂点までの距離は　定数配列    ∞, ０,  ∞,  1。
頂点３の各頂点までの距離は　定数配列    ∞,  2, ０,  5。
頂点４の各頂点までの距離は　定数配列    ∞,  ∞,  ∞, ０。

グラフを初期化するとは （・　→　・）
    出発頂点数最大で　回数指定し
        出発頂点（回数）に　回数を　入れ
    繰り返す
    頂点距離群（１）に　頂点１の各頂点までの距離を　入れ
    頂点距離群（２）に　頂点２の各頂点までの距離を　入れ
    頂点距離群（３）に　頂点３の各頂点までの距離を　入れ
    頂点距離群（４）に　頂点４の各頂点までの距離を　入れる。

ダイクストラ法で最短経路を求めるとは （・　→　・）
        確定判定は   出発頂点数最大の　バイト変数

        最小距離候補の頂点Noは      変数
        最小距離候補は　           変数
        頂点Noは                  変数

    ※距離候補配列を∞で初期化
    出発頂点数最大で　回数指定し
        距離（回数）に　∞を　入れ
        確定判定（回数）を　クリアし　※０を　入れ
    繰り返す
    距離（１）を　クリアし　※０を　入れ

    出発頂点数最大で　回数指定し
        ※ 未確定の中で 距離候補 が最小の頂点 を探す
        最小距離候補に　∞を　入れ
        最小距離候補の頂点Noに　最短頂点未確定を　入れ
        
        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定し
            確定判定（頂点No）が　偽？　かつ　
                    距離（頂点No）が　最小距離候補より　小さい
            ならば
                最小距離候補に　距離（頂点No）を　入れ
                最小距離候補の頂点Noに　頂点Noを　入れ
            つぎに
            頂点Noを　一つ増加し
        繰り返す

        最小距離候補の頂点Noが　最短頂点未確定に　等しい　ならば　打ち切り　つぎに    
        確定判定（最小距離候補の頂点No）を　セットし　※１を　入れ

        ※最小距離候補の頂点 から伸びる辺で 最小距離候補 を更新
        頂点Noに　１を　入れ
        出発頂点数最大で　回数指定
            頂点距離（最小距離候補の頂点No、頂点No）が　∞に　等しい
            でなければ
                距離（最小距離候補の頂点No）に　頂点距離（最小距離候補の頂点No、頂点No）を　加えて　複写し
                ※複写したので加算結果がスタックに２つのっている
                （その１つ目が）　距離（頂点No）より　小さい
                ならば
                （その２つ目を）　距離（頂点No）に　入れ
                さもなければ
                （その２つ目を）　捨て　※入れない場合は捨てる
                つぎに
            つぎに
            頂点Noを　一つ増加
        繰り返す

    繰り返す。

結果を表示するとは （・　→　・）
    「頂点No１からの各頂点の最短距離結果」を　一行表示し
    出発頂点数最大で　回数指定し
        「頂点No：」を　表示し　回数を　数値表示し
        「　距離：」を　表示し  距離（回数）を　数値表示し　改行し
    繰り返す。

メインとは （・　→　・）
    グラフを初期化し
    ダイクストラ法で最短経路を求め
    結果を表示する。

お題のソースコードをコンパイル

では、コンパイルしてみます。Mind8によるコンパイル結果です。

C:\developments\vscode\mind9\algorithm>mind dijkstra file

日本語プログラミング言語 Ｍｉｎｄ Version 8.07 for Windows
          Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> dijkstra.exe

実行結果

実行結果です。

C:\developments\vscode\mind9\algorithm>dijkstra          
頂点No１からの各頂点の最短距離結果
頂点No：1　距離：0
頂点No：2　距離：3
頂点No：3　距離：1
頂点No：4　距離：4

かなり芸のない出力ですが、各頂点への距離が算出されました

おわりに

いかがでしたでしょうか？わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。

1. 演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法（ポーランド記法）+ 1 2、後に記述する後置記法（逆ポーランド記法）1 2 +がある。日本語は１と ２を 足す。 ↩