So here's my attempt at translating that description of an algorithm
into actual Python code ended up using helpful structures
maybe a little different than before so I've got a Dijkstra's algorithm.
Dijkstra is the name of the individual who first described
and analyzed this algorithm for a single-source shortest path.
So we give it a single source. We give it a single node in the network.
Then we ask for the distance to all the other nodes in the network in graph G.
So the distance so far is a structure that's going to represent a mapping
from nodes to what we think the distance might be from V to that node.
And in our hand simulated algorithm, these are the numbers in the non-locked circles.
Some nodes might not have any numbers yet,
and the ones that have numbers are represented in that mapping.
So then we start structure off by saying well, the distance that we know of so far from V to the V,
the node that we started at, is zero, and we do that in the hand simulation as well.
Alright, now, there's an additional data structure, which I call final dist,
which is once we actually figured out what the real distance is,
we stick in this structure and so that's basically the numbers that are in the heavy circles here.
When a circle becomes heavy because I'm locking it down,
I moved that number into the final dist mapping, and I deleted it from the dist so far
so that number doesn't exist anymore in the dist so far mapping.
Now, we're going to iterate as long as the set of nodes
for which we've computed the distance is less than the total number of nodes.
Now, this is a little risky. I probably shouldn't have done this.
Because if the graph is disconnected, what this is going to do is this is how we're going to die.
Well, let's see where it's going to die, but it will keep trying to add nodes
in their final distances even though they aren't final distances to add.
So there's probably other test that might be better to determine
when everything that's reachable has actually been assigned value.
In general, this test isn't quite the right test, but it will suffice for a connected graph
and that's we're going to try it on.
What do we do as long as there's more nodes that we need to analyze,
Take the node that has the shortest distance of all the ones so far, call that w, and lock it down.
Locking it down in this case involves need printing a debugging message
saying that the final distance for w is whatever we computed the distance so far as.
We now know that this is the final distance and then we delete that from the dist so far structure.
Then we go through its neighbors.
All of the neighbors of w in the graphs called an x, and for each one, we'll say,
well, if we completely solved that neighbor then we don't have to do anything,
but if we haven't then see if it has a distance so far, and if it doesn't then give it one
by saying, well, our best guess is the distance.
It's going to be the distance that it took to get to w plus the distance from w to x.
On the other hand, if it already has the distance, check if the new distance,
the distance to w plus the distance from w to x, is better than the distance
that we had so far, and if it is, replace it.
This is sometimes called relaxation. It doesn't seem very relaxing but that's what it is.
And so now we've handled that node.
We handle all the nodes for the neighbors of w and that means we've handled w.
We've locked it down, and we can move on.
We go back up and handle the next node closest to the start state.
And once we've gone through all of the nodes and assigned them all their final distances
then we return that structure and we're done.
This is the Dijkstra's algorithm in a nutshell. Let's analyze this.
तो यहाँ एक एल्गोरिथ्म के उस विवरण का अनुवाद पर मेरा प्रयास है
में वास्तविक अजगर कोड उपयोगी संरचनाओं का उपयोग कर समाप्त हुआ
शायद एक छोटे से अलग से पहले तो मैं एक Dijkstra एल्गोरिथ्म है।
Dijkstra व्यक्ति जो पहले वर्णित का नाम है
और इस एल्गोरिथ्म एक एकल-स्रोत लघुतम पथ के लिए विश्लेषण किया।
तो हम इसे एक ही स्रोत दे। हम इसे एक एकल नोड नेटवर्क में दे।
फिर हम ग्राफ जी में नेटवर्क में अन्य सभी नोड्स के लिए दूरी के लिए पूछना
इतनी दूरी है अब तक एक संरचना है कि एक मानचित्रण का प्रतिनिधित्व करने के लिए जा रहा है
क्या लगता है कि हम दूरी के लिए नोड्स से V से उस नोड के लिए हो सकता है।
और हमारे हाथ नकली एल्गोरिथ्म में, ये गैर-लॉक हलकों में संख्याएँ हैं।
कुछ नोड्स किसी भी संख्या अभी तक नहीं हो सकता है,
और लोगों कि संख्या है कि मैपिंग में प्रतिनिधित्व कर रहे हैं।
तो फिर हम संरचना ठीक है, कि हम V से दूर करने के लिए V पता दूरी कह द्वारा शुरू,
नोड जो हम पर, शुरू कर दिया है शून्य, और हम जो हाथ के अनुकरण में रूप में अच्छी तरह से करते हैं।
ठीक है, अब, वहाँ एक अतिरिक्त डेटा संरचना है, जो मैं अंतिम जिला कहते है,
जो एक बार हम वास्तव में क्या है बाहर असली दूरी लगा है,
हम इस संरचना में लकड़ी और ताकि मूल रूप से नंबर है कि भारी हलकों में यहाँ कर रहे हैं है।
क्योंकि मैं इसे नीचे ताला लगा कर रहा हूँ जब एक सर्कल बन जाता भारी है,
मैं अंतिम जिला मैपिंग में, उस नंबर चले गए और मैं यह अभी तक जिला से हटाए गए
तो यह संख्या अब और अभी तक का मिलान जिला में मौजूद नहीं है।
अब, हम के रूप में लंबे समय के रूप में सेट नोड्स की पुनरावृति जा रहे हैं
जिसके लिए हम नोड्स की कुल संख्या से कम दूरी है परिकलित है।
अब, यह थोड़ा जोखिम भरा है। मैं शायद यह किया जाता है नहीं करना चाहिए।
क्योंकि अगर ग्राफ डिस्कनेक्ट कर दिया गया है, है यह है क्या यह करने के लिए जा रहा है कैसे हम मरने के लिए जा रहे हैं।
ठीक है, चलो देखें जहाँ इसे है मरने के लिए जा रहा है, लेकिन यह जाएगा रखने के प्रयास नोड्स जोड़ने के लिए
उनके अंतिम दूरी में भले ही वे अंतिम दूरी को जोड़ने के लिए नहीं कर रहे हैं।
तो वहाँ शायद अन्य परीक्षण कि यह निर्धारित करने के लिए बेहतर हो सकता है है
जब सब कुछ है कि पहुँच से बाहर है वास्तव में मान असाइन किया गया है।
सामान्य में, यह परीक्षण काफी सही कसौटी नहीं है, लेकिन यह किसी कनेक्ट किए गए ग्राफ के लिए पर्याप्त होगा
और है कि हम यह कोशिश जा रहे हैं।
वहाँ तक है अधिक नोड्स हम का विश्लेषण करने के लिए की जरूरत है कि हम क्या करते हैं,
लेने के नोड है कि सब लोगों की दूरी कम से कम अभी तक है, कहते हैं कि w, और यह नीचे बंद।
यह इस मामले में नीचे बंद खिड़कियां शामिल है की जरूरत है एक डीबगिंग संदेश मुद्रित करना
कह रही है कि डब्ल्यू के लिए अंतिम दूरी जो कुछ भी हम किया है के रूप में अभी तक दूर है।
हम अब जानते हैं कि यह अंतिम दूरी है और तब हम जिला से अब तक कि संरचना को नष्ट।
तो हम उसके पड़ोसी देशों के माध्यम से जाना।
रेखांकन में w के पड़ोसियों के सभी एक एक्स कहा जाता है, और हर एक के लिए, हम कहते हैं कि हूँ,
अगर हम पूरी तरह से उस पड़ोसी हल ठीक, तो हम कुछ भी नहीं है,
लेकिन अगर हम तो नहीं देखते हैं अगर यह अभी तक दूर है, और अगर यह तो यह एक नहीं देता
कह कर, अच्छी तरह से, दूरी हमारी सबसे अच्छा लगता है।
यह कि यह w करने के लिए प्राप्त करने के लिए ले लिया दूरी से अधिक एक्स डब्ल्यू से दूरी होने जा रहा है।
दूसरी ओर, यदि जाँच अगर यह पहले से ही दूरी है, नए दूरी,
w के लिए दूरी से अधिक एक्स, w से दूरी दूरी से बेहतर है
हम अभी तक था, और जगह अगर यह है, कि।
यह कभी कभी विश्राम कहा जाता है। यह बहुत ही आराम नहीं लगता, लेकिन है कि यह क्या है।
और अब तो हम उस नोड भी संभाल लिया है।
इसका मतलब है कि हम नियंत्रित किया जाता है और हम w के पड़ोसियों के लिए सभी नोड्स संभाल डब्ल्यू।
हम इसे नीचे बंद है, और हम आगे बढ़ने कर सकते हैं।
हम वापस जाओ और अगले नोड प्रारंभ की स्थिति के लिए निकटतम संभाल।
और एक बार हम सभी नोड्स के माध्यम से चला गया है और उन्हें उनके सभी अंतिम दूरी असाइन किया गया
फिर हम वापस कि संरचना और हम कर रहे हैं।
यह संक्षेप में Dijkstra एल्गोरिथ्म है। चलो इस का विश्लेषण।
ではアルゴリズムの記述をPythonの
コードに書き換えてみます
今回はダイクストラ法を使います
ダイクストラというのは数学者の名前で
2ノード間の最短経路のアルゴリズムを考案しました
まずはネットワーク上の1個目のノードから
グラフG上の他のノードとの距離を調べます
dist_so_farはvからノードの間の距離の
未確定の値を格納する仕掛けです
以前見た手描きの図では数値が丸の中に
書かれていますが確定していません
まだ数値が入っていないノードも
ありますが確定ししだい値が入ります
最初にvからvへの距離から始めましょう
最初のノードに入る値は0です
この新たなデータ構造はfinal_distとしました
距離が確定したらここに挿入します
太字の丸に入っている値がここに入ることになります
確定したら丸を太い字で囲みます
その数値をfinal_dist に入れてdist_so_farからは削除
dist_so_farの値は空になります
全ノードを参照し終わるまで
距離の算出を繰り返します
少し不具合がありますね
グラフが切れていたら終了してしまうかもしれません
まあそれは置いておいてノードのfinal_distに
値を入れていきます
ここにすべての値が入ったか
調べるテストが必要だったかもしれません
少し修正が必要ですが連結グラフには
十分使えるので
このまま進めます
まだ分析するノードがある間は
最短の距離のノードをwとして確定します
wのfinal_distの値が確定したら
デバッグメッセージを出力します
これでfinal _distが確定しましたから
dist_so_farからは削除します
次に隣接ノードです
すべてのwの隣接ノードはｘと呼びます
隣接ノードがなければ何もしません
まだあればそのノードにdist_so_farの値を入れます
この場合の距離の値は
wまでの距離とｗからｘまでの距離を足したものです
すでに距離に値が入っている場合は
より新しい値がないか調べます
あれば置き換えます
これは緩和法などと呼ばれます
このノードについて処理しました
ｗの隣接ノードを見終わってｗについての
処理が終りました
最初のノードに近いところからまた見ていきます
すべてのノードに最終の距離の値をアサインしたら
これで終了です
ダイクストラ法をざっと確認しました 解析しましょう