As I was describing it before, for each node we do this test to find the shortest distance so far.
That's a heap operation--there's n things in the heap, so this is a logn operation.
So this altogether is going to get run once for each node--so this part of the algorithm
actually takes time and logn.
For each of the edges in the graph, we do this distance reduction operation,
which also is a logn time operation--so that becomes for each edge a logn or mlogn.
Now, both of these have to get done so we actually add these together nlogn and mlogn,
and into the assumption that the graph is connected, this m has to be at least as big as this n--
because this term dominates--so that gives us a total running time of Î(mlogn).
Just I'll mention as an aside, there're some very clever data structure work that's been done
by Fredman and Tarjan, the same Tarjan as before, that allows this actually to be decreased
using a very special kind of heap that allows the running time to become nlogn+m.
We need at least m just to visit all the edges. So this is a pretty remarkable result.
I've implemented this in the past. It didn't run so fast for me.
These are asymptotic results in that the overhead in keeping this fancy heap type
structure updated was more than--well, I wasn't able to implement it so it was efficient enough.
But the heaps that we were talking about the overhead is pretty raw
and we get this kind of running time, the elapse should be pretty efficient.
मैं यह पहले का वर्णन किया गया के रूप में, प्रत्येक नोड के लिए हम इस परीक्षण के लिए दूरी कम से कम अभी तक पता करते हैं।
है कि एक ढेर ऑपरेशन - n बातों के ढेर में है, तो यह एक logn ऑपरेशन है।
तो यह पूरी तरह एक बार प्रत्येक नोड के लिए - भाग लेने के लिए जा रहा है तो यह एल्गोरिथ्म का हिस्सा
वास्तव में समय और logn लेता है।
किनारों के ग्राफ में से प्रत्येक के लिए, हम यह दूरी कम करने कार्रवाई करते हैं,
जो भी एक logn समय ऑपरेशन - है इसलिए कि एक logn या mlogn के लिए प्रत्येक किनारे हो जाता है।
अब, इन दोनों को किया हो तो हम वास्तव में ये एक साथ nlogn और mlogn को जोड़ने के लिए है,
और इस धारणा में कि ग्राफ से जुड़ा है, इस एम इस एन - के रूप में कम से कम में बड़ा हो गया है
क्योंकि यह शब्द हावी - तो कि हमें मैं (mlogn) के समय से चल रहा एक कुल देता है।
मैं एक अलग रूप में, बस उल्लेख करेंगे वहाँ हो गया है कि कुछ बहुत चालाक डेटा संरचना काम किया
Fredman और Tarjan, के रूप में एक ही Tarjan से पहले, कि यह वास्तव में कमी होना करने के लिए अनुमति देता है
समय चल रहा nlogn + m बनने के लिए अनुमति देता है ढेर के एक बहुत ही विशेष प्रकार का उपयोग कर।
पर कम से कम m बस सभी किनारों पर जाएँ हमें। तो यह एक बहुत उल्लेखनीय परिणाम है।
मैं यह अतीत में क्रियान्वित किया है। यह मेरे लिए इतनी तेजी से चला नहीं था।
ये asymptotic परिणाम कर रहे हैं में है कि भूमि के ऊपर रखने के इस फैंसी ढेर में लिखें
से - अच्छी तरह से अधिक संरचना अद्यतन किया गया था, मैं तो यह पर्याप्त सक्षम था इसे लागू करने में सक्षम नहीं था।
लेकिन जो हम भूमि के ऊपर के बारे में बात कर रहे थे ढेर बहुत कच्चा है
और हम इस तरह का समय चल रहा हो, elapse बहुत कुशल होना चाहिए।
各ノードに対して最短距離を見つける処理をします
ヒープで行いますのでここはlog n処理です
これが各ノードに対して行われるので
この部分のアルゴリズムは
n log nに時間がかかります
エッジについては距離短縮の処理を行うので
ここでもlog nの時間がかかります
log nまたはm log nです
さてこのn log nと m log nも加算して
連結グラフという前提で
mは最低でもn以上なはずです
トータルの実行時間はΘ(m log n)です
このデータ構造設計に携わった2名について
言及しておきます
フレッドマンとタージャンがこの構造に貢献しました
特別なヒープを使い実行時間が
n log n+mとなるようにしたのです
最低でもmだけがすべてのエッジに
行けばいいようになりました
以前私がこのような仕組みを実装した時は
複雑なヒープ構造の維持にオーバーヘッドがかかり
漸近的結果しか得られませんでした
しかしこのヒープのオーバーヘッドは小さいので
かなり効率的なはずです