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

はじめに

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

Mind（マインド）

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

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

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

定番アルゴリズム：負閉路検出付きダイクストラ法とは

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

ここではその中のひとつ「負閉路検出付きダイクストラ法」を扱ってみます。「ダイクストラ法」はある頂点から他のすべての頂点への最短距離と経路を求めるためのロジックです。今回は負閉路の存在を検出し警告する実装を考察します。

同様の定番アルゴリズムに「ベルマン‐フォード法」がありますが、頂点間（辺）のコスト：重み≒距離が負数でなければ「優先度付きキューを使ったダイクストラ法」のが速いと言われており、負数がある場合は「ベルマン‐フォード法」が使われるのが一般的です。

では、距離が負数の負閉路があった場合、「優先度付きキューを使ったダイクストラ法」はどのような結果となるのか興味がわいたので実装してみました。

「優先度付きキューを使ったダイクストラ法」は、こちらの記事をご参照ください。本記事はこちらの記事の実装の修正版となります。

お題のソースコード

今回は下記のような負閉路を持った経路を想定します。数字は頂点の番号で４つの頂点があるとします。かっこ値は頂点間の距離（コスト：重み）を意味します。

コスト：重みはおおむね距離（単位：長さ）と考えて問題はありませんが、マイナスのコストを考慮する場合は、その他の属性ウエイト：重みを加味したなんらかの総合値と考えた方がよい場合があります。（距離に近い属性であれば方向とか）

   (4)      (6)        (2)
1 -----> 2 ------> 3 ------> 4
                     ^      |
                     |      |
                     +------+
                        (-7)

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

4頂点 1,2,3,4 かっこ値は頂点間の距離
 1 → 2 (4)
 2 → 3 (6)
 3 → 4 (2)
 4 → 3 (-7)   ← 負閉路 3→4→3

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

※      頂点１　２　３　４
※頂点１    ０, 4,  ∞,  ∞
※頂点２    ∞, ０,  6,  ∞
※頂点３    ∞,  ∞, ０,  2
※頂点４    ∞,  ∞, -7, ０

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

dijkstrapqnegative.src

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

Mindの場合、２次元配列は構造体で定義されます。（引用時は基底の変数名を中かっこでインデックス１、２で表現します。）

dijkstrapqnegative.src

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

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

前記の状態に配列を初期化します。

dijkstrapqnegative.src

グラフを初期化するとは （・　→　・）　本定義
        頂点No１は　変数
        頂点No２は　変数

    頂点No１に　１を　入れ
    頂点数最大で　回数指定し
        頂点No２に　１を　入れ
        頂点数最大で　回数指定し          
            頂点No１と　頂点No２が　等しい
            ならば
                頂点距離（頂点No１、頂点No２）に　０を　入れ
            さもなければ
                頂点距離（頂点No１、頂点No２）に　∞を　入れ
            つぎに
            頂点No２を　一つ増加
        繰り返す
        頂点No１を　一つ増加
    繰り返し
    頂点距離（１、２）に　４を　入れ
    頂点距離（２、３）に　６を　入れ
    頂点距離（３、４）に　２を　入れ
    頂点距離（４、３）に　－７を　入れること。

負閉路の検出は単純で、上記の頂点距離の値がマイナスの場合をループで検知します。

dijkstrapqnegative.src

負閉路を検出するとは （・　→　真偽）　本定義
        検出済は        変数
        頂点No１は　変数
        頂点No２は　変数

    検出済を　クリアし
    頂点No１に　１を　入れ
    頂点数最大で　回数指定し
        頂点No２に　１を　入れ
        頂点数最大で　回数指定し          
            頂点距離（頂点No１、頂点No２）が　０より　小さい
            ならば
                検出済を　セットし
                打ち切り
            つぎに
            頂点No２を　一つ増加
        繰り返す
        頂点No１を　一つ増加
    繰り返し
    検出済を　返すこと。

負閉路を検出した場合は警告メッセージを表示します。本来は負閉路が存在した場合の「ダイクストラ法」の結果は正しくないので、実行を中断することが望ましいのですが、今回はどのような結果となるかを観測するため、続けて実行します。

dijkstrapqnegative.src

メインとは （・　→　・）
    グラフを初期化し
    負閉路を検出した
    ならば
        「負閉路の存在を検出しました。ダイクストラ法の結果は正しくありません。」を　一行表示し
    つぎに
    ダイクストラ法で最短経路を求め
    結果を表示する。

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

pq4dijkstra.srcはダイクストラ法向けの優先度付きキューのライブラリファイルとなります。下記の記事をご参照ください。

仮定義を使ってメインが冒頭に来るようにして、各処理の実装はその後で定義してみました。

dijkstrapqnegative.src

"pq4dijkstra"を　コンパイルする。

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

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

頂点間距離は  頂点数最大の　変数。
訪問済みは　頂点数最大の　変数。


グラフを初期化するとは （・　→　・）　仮定義。
負閉路を検出するとは （・　→　・）　  仮定義。
ダイクストラ法で最短経路を求めるとは （・　→　・）　仮定義。
結果を表示するとは （・　→　・）　　　仮定義。

メインとは （・　→　・）
    グラフを初期化し
    負閉路を検出した
    ならば
        「負閉路の存在を検出しました。ダイクストラ法の結果は正しくありません。」を　一行表示し
    つぎに
    ダイクストラ法で最短経路を求め
    結果を表示する。

グラフを初期化するとは （・　→　・）　本定義
        頂点No１は　変数
        頂点No２は　変数

    頂点No１に　１を　入れ
    頂点数最大で　回数指定し
        頂点No２に　１を　入れ
        頂点数最大で　回数指定し          
            頂点No１と　頂点No２が　等しい
            ならば
                頂点距離（頂点No１、頂点No２）に　０を　入れ
            さもなければ
                頂点距離（頂点No１、頂点No２）に　∞を　入れ
            つぎに
            頂点No２を　一つ増加
        繰り返す
        頂点No１を　一つ増加
    繰り返し
    ※ 隣接行列（4頂点 1,2,3,4 かっこ値は頂点間の距離）
    ※ 1→2(4)
    ※ 2→3(6)
    ※ 3→4(2)
    ※ 4→3(-7)
    頂点距離（１、２）に　４を　入れ
    頂点距離（２、３）に　６を　入れ
    頂点距離（３、４）に　２を　入れ
    頂点距離（４、３）に　－７を　入れること。

負閉路を検出するとは （・　→　真偽）　本定義
        検出済は        変数
        頂点No１は　変数
        頂点No２は　変数

    検出済を　クリアし
    頂点No１に　１を　入れ
    頂点数最大で　回数指定し
        頂点No２に　１を　入れ
        頂点数最大で　回数指定し          
            頂点距離（頂点No１、頂点No２）が　０より　小さい
            ならば
                検出済を　セットし
                打ち切り
            つぎに
            頂点No２を　一つ増加
        繰り返す
        頂点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 dijkstrapqnegative file

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

実行結果

実行結果です。

C:\developments\vscode\mind9\algorithm>dijkstrapqnegative
負閉路の存在を検出しました。ダイクストラ法の結果は正しくありません。
頂点No１からの各頂点の最短距離結果
頂点No：1　距離：0
頂点No：2　距離：4
頂点No：3　距離：5
頂点No：4　距離：12

かなり芸のない出力ですが、各頂点への距離が算出されました負閉路があった場合のダイクストラ法はその存在を無視するようです。

おわりに

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

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