グラフの晦には、掳拉として眶猛が涂えられることがある。この眶猛のことを脚み∈weight∷という。この脚みは2爬粗のコストや墓さなどを罢蹋することが驴い。
グラフの2爬粗を冯ぶ烯のうちで、脚みの另下が呵井となる苹界を滇める啼玛を呵没烯啼玛という。これは、苹烯讨における2爬粗の调违の呵井猛、ネットワ〖クの奶慨讨の搀俐联买数恕など、炳脱认跋は弓い。
ここで雇えるのは、脚みの烧いた铜羹グラフである。
ダイクストラ恕∈Dijkstra's algorithm∷は、呵没烯啼玛の洛山弄なアルゴリズムの办硷である。答塑弄な雇え数は、称爬への呵没烯を叫券爬に夺いところから、界肌澄年していく数恕である。
称收に调违の烧いた脚み烧きの铜羹グラフ惧で扦罢の2爬粗の呵没调违を滇め、呵姜弄にはすべての泪への呵没调违を滇めるアルゴリズムである。幌爬から钨にある爬を界肌茅っていき、冯蔡弄に回年した叫券の泪から链婶の泪への呵没调违が滇められる。
[输怪]ダイクストラ恕を贷梦と簿年した啼玛が、答塑攫鼠やソフ倡などの获呈啼玛によく叫玛されている。
毋¨肌のグラフにおいて、ダイクストラ恕を蝗って、v1から称爬への呵没调违を滇める。
ダイクストラ恕で呵没调违を滇めるには、叫券爬からの呵没调违のわかっている爬の礁圭Sと、Sに崔まれるいずれかの爬に钨儡する爬の礁圭∈Sの董肠と钙ぶ∷について呵没调违に簇する雇弧を裁えながら、靳」にSに崔まれる爬を笼やして、すべての爬に滦する呵没调违を滇めていく。
1¨まずSには叫券爬であるv1だけが崔まれているとして雇弧を渴める。この眷圭、Sの董肠はv2,v3,v4の3爬がある。それぞれの调违は8,5,3である。この面の呵没调违はv1ⅹv4の3なので、v4を糠たにSに崔めることになる。
2¨S={v1,v4}なので、Sの董肠は{v2,v3}となる。SとSの董肠の呵没调违を雇える∈沸统もあることに庙罢∷。v1からのスタ〖トしたときの木儡の调违は8,5であるが、v4を沸统すればv1ⅹv4ⅹv2∈调违7♂5+2∷、v1ⅹv4ⅹv3∈调违4♂3+1∷となる。この面の呵没调违はv1ⅹv4ⅹv3の调违4である。よって、v3がSに裁えられる。
3¨S={v1,v3,v4}なので、Sの董肠は{v2}となる。v2までの调违を滇める。v1ⅹv2∈调违8∷、v1ⅹv3ⅹv2∈调违7∷、v1ⅹv4ⅹv3ⅹv2∈调违6∷なので、呵没调违は6であり、≈v1ⅹv4ⅹv3ⅹv2∽が呵没调违となる沸烯になる。
