まず、有名なSleepSortを思い出してください。 これは数値ソートアルゴリズムですが、QuickSortやMergeSortなどの「従来の」ソートとは大きく異なります。 アルゴリズムは次のように機能します。各番号に比例した遅延を入れてから、各番号のストリームを開始し、割り当てられた時間待機してから、その番号を出力します。 数字が昇順で並べ替えられることは簡単に理解できます。 比較のために時間を前方に移動するだけなので（とにかくこのモデルでは）、この並べ替えに非常に面白いです。
そして、ダイクストラアルゴリズムを思い出しましょう。 多くの人はそれが何であるかを知っていますが、それでもなお、それは正のエッジ重みを持つグラフで最小パスを見つけるためのアルゴリズムです。 距離を探したい頂点の集合をAとします。 アルゴリズムの結果は、このセットから各頂点までの最小距離と、最小パス内の祖先の表示になります。
アルゴリズムは簡単です：
- セットAの場合、答えは明確です（明らかな理由でゼロです）。
- 別の頂点の答えを得る：セットに隣接する頂点から始まりに最も近い頂点を探しましょう。答えは明確で、その答えを覚えておいてください。 彼らにとって、距離は簡単に見つけることができます。それは属の値と接続リブの重量で構成されています。 これは、各反復に関連する最小値を維持することで簡単に達成できます。
このようにして構築された答えが正しいことを証明するのは簡単です。
しかし、SleepSortで最上部に最も近い頂点を探すとどうなりますか？ このように想像できます。「グラフに沿って流れる水」に、その重みに比例して時間的にエッジを通過させるようにします。 セットAから「注ぐ」。その後、「水の起動」から特定のピークに到達するまでの時間（ソート可能なピークのセットからだが、到達できるのはそれだけ）は、前のピークに到達する時間とrib骨の通過時間の合計になります。ダイクストラのアルゴリズムステップでピークを並べ替える特性（これはSleepSortです。「水が到達しました」、これは「スリープ（前+エッジ）;水を取得;」です）。
明らかに、「さらに進む水」は、アルゴリズムの次の反復を実行します。すでに浸水しているピークの近くから最も近いピークを再度検索します。 そして、あるピークまでのパスは、ダイクストラアルゴリズムを使用して正式に検出されます。
したがって、ダイクストラのアルゴリズムは「骨髄に物理的」であることが明らかになります。
私の謙虚な意見では、放電（稲妻）のようなものは、この方法で、つまりダイクストラのアルゴリズム+転送時間で、その方法を探します。
雷が最も抵抗の少ない経路を通る理由の説明
誰かがそれを修正するかもしれませんが、私はそれをこのように理解します：先行電荷は通常の不均一な導体のように伝播します。つまり、最小抵抗の経路に沿った先行電荷の「電流」が最大になることを意味します（各点の近くに非常に多くの平行線を想像すると、この結果が出力されます学校の物理学のコースから）、それはゼロではないことを意味し、これはこの場所でさらに放電があることを意味します。
このアイデアが知識のある人にとって興味深いものであり、初心者がアルゴリズムの動作をより明確に想像するのに役立つことを願っています。