If you did this a little bit carelessly, you might say that
the first number that goes into E is the length of the shortest hot path from A to E,
which in this case would be, well there's two ways to get
the distance 11 to here in two hops and then another seven.
You might have said 18, but in fact, it won't expand D into E until it knows the shortest distance to D,
and the shortest distance is going to be 10 because we can go this way.
four plus one is five and five is 10 so it should be 17,
but let's actually simulate and see what happens.
We expand out A into C and B and once we've done that,
the shortest non-completed distance is the one to C so we're going to lock that down
and then we expand from that node C
There is two edges to incomplete nodes, C to D and C to B.
The C to B has a length of one plus length of four, we already had
that actually improves this one to five and a new node joins the picture, D
and C to D is seven on top of the four we already had for a total of 11.
Alright, of the non-completed nodes, B and D,
the one with the smallest distance is B with distance of five.
We can lock that down and look at the outgoing edges from B,
which is just this one that goes to D which had the length of five
plus the five we already had for a length of 11 in D, which improves D, 10
and this the only node hit that we can read at this point that we haven't completed yet
so we can lock it down, expand out its neighbors, which are F and E.
F gets 20 and E gets the 17 and not only is that the first number written in E but it is the final one
because the very next thing we lock down is E's distance.
We don't lock down F's distance until we actually discover that
there is a shorter path, the 19-length path.
All right, so I think you understand this well enough that we can try to code it up
यदि आप यह थोड़ा सा लापरवाही किया था, तुम कह सकता है
पहली संख्या है कि ई में चला जाता है A से कम से कम गर्म पथ ई की लंबाई है,
जो इस मामले में किया जाएगा, अच्छी तरह से प्राप्त करने के दो तरीके है
दूरी 11 दो hops और फिर एक और सात में यहाँ के लिए।
आप 18 ने कहा कि हो सकता है, लेकिन वास्तव में, यह ई में विस्तार D नहीं होगा जब तक यह दूरी D के लिए कम से कम जानता है,
और दूरी कम से कम 10 हो सकता है क्योंकि हम इस तरह से जा सकते हैं करने के लिए जा रहा है।
चार से अधिक एक पाँच है और पांच 10 है, तो यह 17 होना चाहिए,
लेकिन हम वास्तव में अनुकरण और देखो क्या होता है।
हम बाहर A C और B में और एक बार हम किया है कि विस्तार,
C के लिए एक दूरी कम से कम गैर-पूरा हो गया है इसलिए हम कि नीचे बंद करने के लिए जा रहे हैं
और फिर हम उस नोड C से विस्तार
वहाँ दो किनारों के अपूर्ण नोड्स, सी डी और सी बी करने के लिए के लिए है
C B करने के लिए एक लंबाई में से एक है से अधिक लंबाई चार, हम पहले से ही था
कि वास्तव में करने के लिए यह एक पांच में सुधार है और एक नए नोड चित्र, D में मिलती है
और C D के लिए सात चार हम पहले से ही कुल 11 के लिए किया था के शीर्ष पर है।
ठीक है, गैर-पूर्ण नोड्स की, बी और डी,
छोटी से छोटी दूरी के साथ एक बी के साथ पांच की दूरी है।
हम कि नीचे बंद कर सकते हैं और बाहर जाने वाले किनारों पर B से देखो,
जो सिर्फ इस एक है कि डी जो पांच की लंबाई था करने के लिए चला जाता है
हम पहले से ही था 11 D इंच की लंबाई के लिए पांच प्लस, जो D, 10 में सुधार
और यह कि हम इस बिंदु पर कि हम अभी तक पूरा नहीं पढ़ सकते हैं केवल नोड मारा
इसलिए हम यह नीचे बंद कर सकते हैं, अपने पड़ोसियों, जो F और ई. रहे हैं बाहर का विस्तार
20 एफ हो जाता है और ई 17 हो जाता है और न केवल यह है कि पहली संख्या लिखा है लेकिन यह ई में अंतिम एक है
क्योंकि अगले ही बात हम लॉक डाउन है ई दूरी है।
हम एफ की दूरी नीचे अवरोधित न करें जब तक हम वास्तव में पता चलता है कि
वहाँ एक छोटा पथ, 19-लंबाई पथ है।
सभी सही है, तो मुझे लगता है कि आप समझ में यह अच्छी तरह से पर्याप्त कि हम ऊपर कोड यह करने की कोशिश कर सकते हैं
注意深く考えないとEに行くまでの
最短の回数を選んでしまうかもしれません
この場合だとAから2つパスが考えられますが
Dまで2回の移動で11に7を加算して
18と答えてしまった人はいませんか 正しくは最初にDまでの最小の距離を考えます
このパスを行けば最小の値は10です
4+1+5=10なので7を加算して17になります
シミュレートしてみましょう
まずAからCとBに展開します
最短のCをマークして確定します
次はCからエッジを展開します
CからはDまたはBにエッジが引けます
CからBのパスは1の重さがあり4を加算すると
この値を5にして新しいノードDを追加します
CからDは7なので4+7で11になってしまいます
つまりまだ到達していないノードBとDでは
Bまでのトータル5が最も小さい値になります
ここもマークして今度はBからは
Dに至る1本のパスしかありません 値は5です
5を加算するとDまでの値が11から10に向上しました
他にBから展開できるノードはありません
これもマークして今度はFとEに展開します
Fへは20でEまでは17です
Eからの距離を特定するまでは
Fを確定できません
より短いパスの値は19です
理解できたところでコードにしてみましょう