Teh­tä­vä:
Ly­him­män rei­tin et­sin­tä

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Täs­sä teh­tä­väs­sä har­joi­tel­laan al­go­rit­meis­ta päät­te­le­mis­tä käyt­täen esi­merk­ki­nä te­ho­kas­ta al­go­rit­mia, jo­ka löy­tää ly­him­män ajo­rei­tin. Päät­te­lyt pu­re­taan pie­nik­si as­ke­lik­si, jot­ta sel­lai­set tär­keät pik­ku­asiat tu­li­si­vat nä­ky­vik­si, jot­ka usein ole­te­taan jo osa­tuik­si ja sik­si ohi­te­taan no­peas­ti.

Täs­sä teh­tä­väs­sä Math­Checkiä käy­te­tään toi­si­naan sil­lä ta­val­la vää­rin, et­tä ky­sy­myk­ses­sä esiin­ty­vän tie­don tyyp­pi on jo­ta­kin muu­ta kuin mi­tä Math­Check luu­lee. Sik­si vir­he­il­moi­tuk­set voi­vat jos­kus ol­la kum­mal­li­sia. Esi­mer­kik­si jos ky­sy­tään, kuin­ka mon­ta al­kio­ta on jou­kos­sa Q, niin oi­kea vas­taus on |Q|. Math­Check voi­daan lait­taa tar­kas­ta­maan, et­tä vas­taus on |Q|. Kui­ten­kin Math­Checkil­le Q on lu­ku, jo­ten jos opis­ke­li­jan vas­taus on vää­rin, niin Math­Check an­taa vas­ta­esi­mer­kis­sä Q:lle lu­ku­ar­von, kun pi­täi­si an­taa jouk­ko.

1. Kar­tan esit­tä­mi­nen
2. Al­go­rit­min muut­tu­jat ja nii­den ken­tät
3. Al­go­rit­mi ja pik­ku­tie­to­ja sen toi­min­nas­ta
4. Al­go­rit­mi ei tee lait­to­mia toi­min­to­ja
5. Al­go­rit­mi py­säh­tyy
6. Löy­de­tyt rei­tit to­del­la ovat reit­te­jä
7. Jos reit­te­jä on, al­go­rit­mi löy­tää jon­kin
8. Löy­det­ty reit­ti on mah­dol­li­sim­man ly­hyt
9. To­teu­tus­yk­si­tyis­koh­dis­ta

Kar­tan esit­tä­mi­nen

Kaik­ki kar­tan tie­dot ei­vät ole olen­nai­sia ly­him­män ajo­rei­tin et­si­mi­sen kan­nal­ta. Olen­nai­set tie­dot voi­daan esit­tää sol­muis­ta ja kaa­ris­ta koos­tu­va­na ra­ken­tee­na seu­raa­vas­ti:

• Läh­tö, maa­li ja ris­teyk­set esi­te­tään sol­mui­na.
• Sol­mu­jen vä­li­set tien­pät­kät esi­te­tään kaa­ri­na. Mis­tä kol­mes­ta tie­dos­ta kaa­ri koos­tuu? Mie­ti it­se tai pa­lau­ta mie­leen ai­kai­sem­mis­ta opin­nois­ta, ja sit­ten kat­so vas­taus täs­täsol­mu jos­ta se al­kaa, sol­mu jo­hon se päät­tyy, ja kaa­ren pi­tuus. seu­raa­va ky­sy­mysMin­kä tyyp­pi­nen tie­to kaa­ren pi­tuus on? sen vas­tausei-ne­ga­tii­vi­nen lu­ku

Kaa­ret ovat yk­si­suun­tai­sia, kos­ka …tien­pät­kät voi­vat ol­la yk­si­suun­tai­sia, ku­ten liit­ty­mien ram­pit ja yk­si­suun­tai­set ka­dut kau­pun­geis­sa. Kak­si­suun­tai­nen tien­pät­kä esi­te­tään näinkah­del­la kaa­rel­la, yk­si kum­paan­kin suun­taan.

Reit­tien pi­tuuk­sis­ta pu­hut­taes­sa käy­täm­me sym­bo­lia ∞ (reaa­li­lu­ku­jen ää­re­tön) tar­koit­ta­maan, et­tä pu­hee­na ole­vien sol­mu­jen vä­lil­le ei ole vie­lä löy­det­ty yh­tään reit­tiä pu­hee­na ole­vaan suun­taan. Suu­ruus­jär­jes­tys­ver­tai­luis­sa ∞ tul­ki­taan …suu­rem­mak­si kuin mi­kään lu­ku. Sen an­sios­ta, kun ver­ra­taan juu­ri löy­det­tyä reit­tiä par­haa­seen jo tun­net­tuun, ei tar­vi­ta mo­ni­mut­kais­ta muo­toa ”jos tä­tä en­nen ei ole löy­det­ty mi­tään reit­tiä tai jos nyt löy­det­ty on ly­hyem­pi kuin ly­hyin ai­kai­sem­min löy­det­ty”, vaan tä­mäjos nyt löy­det­ty on ly­hyem­pi kuin ly­hyin ai­kai­sem­min löy­det­ty yk­sin­ker­tai­sem­pi ver­tai­lu riit­tää.

Al­go­rit­min muut­tu­jat ja nii­den ken­tät

Al­go­rit­mi et­sii mah­dol­li­sim­man ly­hyen rei­tin sol­mus­ta l (läh­tö) sol­muun m (maa­li). Jo­kai­seen sol­muun w liit­tyy vii­si tie­toa, jois­ta kak­si en­sim­mäis­tä ei­vät voi muut­tua al­go­rit­min suo­ri­tuk­sen ai­ka­na:

Se, mi­kä esi­tet­tiin edel­lä w↑k, esi­te­tään C-kie­les­sä w->k. C:n ta­pa oli­si teh­nyt kaa­vois­ta se­ka­van nä­köi­siä. Va­lit­tu esi­tys­ta­pa muis­tut­taa Pas­ca­lin syn­tak­sia w^k.

Al­go­rit­mis­sa esiin­ty­vät sol­mut voi­daan to­teut­taa mo­nel­la ta­val­la. Teks­tin pi­tä­mi­sek­si yk­sin­ker­tai­se­na ole­tam­me jat­kos­sa, et­tä ne on to­teu­tet­tu tie­tuei­na tai olioi­na, joi­hin vii­ta­taan osoit­ti­mil­la. Jos osoit­ti­met ei­vät ole tut­tu asia, lue tä­mä.Osoi­tin on ikään kuin osoi­te: se on tie­to jo­ka ker­too, mis­tä jo­kin tie­to löy­tyy. Eiffel-tor­ni si­jait­see osoit­tees­sa Champ de Mars, 5 Avenue Anatole France, 75007 Paris, France. Si­joi­tus u↑e := v on rin­nas­tet­ta­vis­sa sii­hen, et­tä ko­pioi­daan teks­tin­pät­kä ”Champ de Mars, 5 Avenue Anatole France, 75007 Paris, France” paik­kaan u↑e sen si­jaan et­tä paik­kaan u↑e ra­ken­net­tai­siin ko­pio Eiffel-tor­nis­ta. (Jäl­kim­mäis­tä­kin har­ras­te­taan.) Vaik­ka esi­merk­ki on has­su, se ku­vas­taa sil­ti se­kä osoit­ti­mien toi­min­taa et­tä nii­den käy­töl­lä saa­vu­tet­ta­vis­sa ole­via hyö­ty­jä. Esi­mer­kik­si w tar­koit­taa osoi­tin­ta ja w↑k eräs­tä osoit­ti­men w ta­kaa löy­ty­vän tie­tueen kent­tää. Tär­keää on, et­tä si­joi­tus u↑e := v ei tar­koi­ta sol­mun v kaik­kien tie­to­jen ko­pioin­tia paik­kaan u↑e, vaan to­del­la­kin esi­mer­kik­si sol­muun v koh­dis­tu­van osoit­ti­men ko­pioin­tia.

Sa­ma in­for­maa­tio voi­daan usein esit­tää eri ta­voil­la. Se, mi­kä on kä­te­vin­tä ma­te­ma­tii­kas­sa, ei vält­tä­mät­tä ole pa­ras ta­pa oh­jel­moin­nis­sa. Esi­tys­ta­vat esit­tä­vät sa­man in­for­maa­tion, jos ja vain jos nii­den vä­lil­lä on sel­lai­set muun­nok­set kum­paan­kin suun­taan, et­tä kun aloi­te­taan en­sim­mäi­ses­tä esi­tys­ta­vas­ta, muun­ne­taan toi­seen esi­tys­ta­paan, ja muun­ne­taan en­sim­mäi­seen esi­tys­ta­paan, niin saa­daan se mis­tä aloi­tet­tiin; ja kun aloi­te­taan toi­ses­ta esi­tys­ta­vas­ta, muun­ne­taan en­sim­mäi­seen esi­tys­ta­paan, ja muun­ne­taan toi­seen esi­tys­ta­paan, niin saa­daan se mis­tä aloi­tet­tiin. Lu­vus­sa 1 ja täs­sä lu­vus­sa käy­tet­ty­jen esi­tys­ta­po­jen ta­pauk­ses­sa nä­mä muun­nok­set ovat:

E  =  { (w, u, p) | w ∈ V ∧ (u, p) ∈ w↑kaaret }

Jos w ∈ V, niin  w↑kaaret  =  …{ (u, p) | (w, u, p) ∈ E }

Q on prio­ri­teet­ti­jo­no, eli tie­to­ra­ken­ne, jo­ka tar­joaa kak­si pal­ve­lua: al­kion li­sää­mi­sen ja prio­ri­tee­til­taan mah­dol­li­sim­man suu­ren al­kion pois­ta­mi­sen. Täs­sä ta­pauk­ses­sa li­sät­tä­vät al­kiot ovat pa­re­ja, jot­ka koos­tu­vat osoit­ti­mes­ta sol­muun ja lu­vus­ta. Al­kion prio­ri­teet­ti on si­tä suu­rem­pi, mi­tä pie­nem­pi sii­hen kuu­lu­va lu­ku on. Toi­min­to (v, x) := Q.poista_eka() va­lit­see al­kion, jon­ka lu­ku on mah­dol­li­sim­man pie­ni, si­joit­taa osoit­ti­men muut­tu­jaan v ja lu­vun muut­tu­jaan x se­kä pois­taa al­kion Q:sta.

Mik­si edel­lä sa­not­tiin ”prio­ri­tee­til­taan mah­dol­li­sim­man suu­ren” ei­kä ”prio­ri­tee­til­taan suu­rim­man”? vas­tausVoi ol­la, et­tä mo­nel­la al­kiol­la on sa­ma prio­ri­teet­ti, jo­ta suu­rem­paa prio­ri­teet­tia ei ole mil­lään al­kiol­la. Esi­mer­kik­si läh­dön ja maa­lin vä­lil­lä voi ol­la kak­si yh­tä ly­hyt­tä reit­tiä, joi­ta ly­hyem­piä reit­te­jä ei ole.

Alus­sa Q on tyh­jä. Q:n to­teu­tus­ta kä­si­tel­lään him­pun ver­ran lu­vus­sa 9. To­teu­tus­yk­si­tyis­koh­dis­ta. |Q| tar­koit­taa Q:ssa ole­vien al­kioi­den mää­rää.

Al­go­rit­mi ja pik­ku­tie­to­ja sen toi­min­nas­ta

 1  l↑d := 0
 2  Q.lisää(l, l↑a)
 3  v := l
 4  while |Q| ≠ 0 ∧ v ≠ m do
 5      (v, x) := Q.poista_eka()
 6      if ¬v↑k then
 7          v↑k := T
 8          for (u, p) ∈ v↑kaaret do
 9              if u↑d > v↑d + p then
10                  u↑d := v↑d + p
11                  u↑e := v
12                  Q.lisää(u, u↑d + u↑a)

Vaik­ka et vie­lä ym­mär­täi­si juu­ri mi­tään al­go­rit­min toi­min­nas­ta, voit sil­ti hel­pos­ti var­mis­tua sii­tä, et­tä min­kään sol­mun ↑kaaret ja ↑a ei­vät muu­tu al­go­rit­min suo­ri­tuk­sen ai­ka­na. Mi­ten?Al­go­rit­mi lä­pi sil­mäi­le­mäl­lä on help­po var­mis­tua, et­tä mis­sään ei ole si­joi­tus­ta, jo­ka koh­dis­tuu min­kään sol­mun kaaret-kent­tään tai a-kent­tään. Tä­mä kik­ka on usein hyö­dyl­li­nen al­go­rit­mei­hin tu­tus­tut­taes­sa.

Ylei­ses­sä ti­lan­tees­sa on otet­ta­va huo­mioon mah­dol­li­suus, et­tä jo­hon­kin tie­toon si­joi­te­taan jo­tain muu­ta saan­ti­pol­kua käyt­täen kuin tie­don en­si­si­jai­sel­la ni­mel­lä. Tä­mä on iso ai­he­pii­ri, jo­hon ei voi­da täs­sä pa­neu­tua. Yh­den esi­mer­kin kui­ten­kin ker­ron: vaik­ka alus­sa l↑k = F ei­kä al­go­rit­mis­sa ole si­joi­tus­ta muo­toa ”l↑k :=”, sil­ti yh­tä poik­keus­ta lu­kuun ot­ta­mat­ta lo­pus­sa pä­tee l↑k = T. Mi­kä on tä­mä poik­keus­ta­paus? vas­tausJos l = m eli läh­tö on sa­ma kuin maa­li, niin al­go­rit­mi lo­pet­taa kun ri­vil­le 4 tul­laan en­sim­mäi­sen ker­ran. Mik­si muis­sa ta­pauk­sis­sa lo­pus­sa l↑k = T? vas­tausKun ri­vil­le 4 tul­laan en­sim­mäi­sen ker­ran, v = l ja Q si­säl­tää (vain) pa­rin (l, x) jol­le­kin x. Jos l ≠ m, niin men­nään sil­mu­kan si­sään. Ri­vil­lä 5 si­joi­te­taan v:hen l, mi­kä ei muu­ta v:n ei­kä l↑k:n ar­voa. Pää­dy­tään ri­vil­le 7, jos­sa si­joi­te­taan l↑k := T.

Täs­sä al­go­rit­mis­sa on mui­ta­kin muut­tu­jia ja/tai kent­tiä, joi­den ar­vo ei mis­sään ti­lan­tees­sa muu­tu. Mit­kä?l ja m eli läh­tö ja maa­li.

Edel­lä to­de­tus­ta seu­raa myös, et­tä ri­vin 12 alus­sa u↑d ≠ ∞. Syy on tä­mäRi­vil­le 12 ei tul­la, el­lei ri­vil­lä 9 to­det­tu, et­tä u↑d:hen si­joi­tet­ta­vak­si tar­koi­tet­tu ar­vo on u↑d:n ai­kai­sem­paa ar­voa pie­nem­pi. Kos­ka ∞ on suu­rin mah­dol­li­nen ar­vo, se ei voi ol­la ai­kai­sem­paa ar­voa pie­nem­pi..

Ol­koon w mi­kä ta­han­sa sol­mu. Sa­nom­me, et­tä al­go­rit­mi löy­tää w:n sil­lä het­kel­lä kun w↑d lak­kaa ole­mas­ta ∞. Jo­kai­nen sol­mu on alus­sa löy­tä­mät­tä, kos­ka lu­vus­sa 2 ker­rot­tiin, et­tä w↑d on aluk­si ∞. Löy­ty­nyt sol­mu ei voi muut­tua ta­kai­sin löy­tä­mät­tö­mäk­si. Mik­si?Edel­lä näim­me, et­tä w↑d ei voi kas­vaa. Sik­si w↑d ei voi pa­la­ta ta­kai­sin ar­voon, jo­ka sil­lä on aiem­min ol­lut mut­ta ei ole enää.

Ku­ten edel­lä to­det­tiin, Q ei si­säl­lä sol­mu­ja ei­kä osoit­ti­mia sol­mui­hin vaan pa­re­ja (w, x), mis­sä w on osoi­tin sol­muun ja x on lu­ku. Täl­lai­sis­ta pa­reis­ta pu­hu­mi­nen oli­si kui­ten­kin jat­kos­sa usein köm­pe­löä. Sik­si so­vim­me, et­tä il­maus ”w on Q:ssa” tar­koit­taa, et­tä on ole­mas­sa sel­lai­nen x, et­tä (w, x) on Q:ssa.

Seu­raa­va väi­te pä­tee ko­ko ajan. Mik­si?Lu­vus­sa 2 lu­vat­tiin, et­tä alus­sa Q on tyh­jä. Sik­si alus­sa mi­kään sol­mu ei ole ei­kä ole ol­lut Q:ssa, jo­ten väi­te pä­tee. Sol­mu­ja li­sä­tään Q:hun vain ri­veil­lä 2 ja 12. Kum­mas­sa­kin ta­pauk­ses­sa on edel­tä­vil­lä ri­veil­lä var­mis­tet­tu, et­tä sol­mun d-ken­tän ar­vo ei ole ∞. Ku­ten edel­lä to­det­tiin, se ei voi pa­la­ta ar­voon ∞.

Jo­kai­sel­le sol­mul­le w, jo­ka on tai on ol­lut Q:ssa, pä­tee w↑d ≠ ∞.

Kun sa­nom­me, et­tä sol­mu kä­si­tel­lään, tar­koi­tam­me, et­tä ri­vit 7, …, 12 suo­ri­te­taan si­ten, et­tä v osoit­taa ko. sol­muun. Vaik­ka et vie­lä ym­mär­täi­si juu­ri mi­tään al­go­rit­min toi­min­nas­ta, voit sil­ti hel­pos­ti var­mis­tua sii­tä, et­tä ku­kin sol­mu kä­si­tel­lään enin­tään ker­ran. Mi­ten?Ri­vin 6 vuok­si sol­mu kä­si­tel­lään vain, jos sen k-ken­tän ar­vo on F. Ri­vin 7 vuok­si k-ken­tän ar­vok­si tu­lee T. Mis­sään ei ole lau­set­ta, jo­ka voi­si muut­taa k-ken­tän ar­von ta­kai­sin F:ksi, jo­ten sol­mu ei voi lä­päis­tä ri­vin 6 tes­tiä tois­ta ker­taa.

Al­go­rit­mi ei tee lait­to­mia toi­min­to­ja

Seu­raa­vak­si var­mis­tam­me, sil­tä osin kuin asian var­mis­ta­mi­nen kuu­luu al­go­rit­mi­suun­nit­te­lun pii­riin, et­tä al­go­rit­mi ei mil­loin­kaan yri­tä suo­rit­taa lai­ton­ta toi­min­toa, ku­ten nol­lal­la ja­ka­mis­ta.

Osoit­ti­met l, m, u ja v osoit­ta­vat ai­na sol­mui­hin (eli ei­vät voi saa­da ar­voa nil). Al­go­rit­mi ei it­se käy­tä e-kent­tiä. Sik­si mi­kään kent­tien va­lin­ta ope­raat­to­ril­la ↑ ei ole lai­ton.

Ri­vien 1, 3, 7 ja 11 si­joi­tus­lau­seet ei­vät voi ol­la lait­to­mia.

Li­sät­täes­sä sol­mu­ja Q:hun ri­veil­lä 2 ja 12 muis­ti voi lop­pua kes­ken. Tä­mä on tär­keä asia, mut­ta hoi­de­taan yleen­sä muual­la kuin al­go­rit­mi­suun­nit­te­lus­sa tai jä­te­tään ko­ko­naan hoi­ta­mat­ta.

Ri­vien 4, 6 ja 8 tes­tit ja sa­mal­la ko­ko ri­vit ovat on­gel­mat­to­mia.

Tie­to­ra­ken­tees­ta pois­ta­mi­nen on lai­ton toi­min­to, jos …tie­to­ra­ken­ne on tyh­jä. Ri­vil­lä 5 tä­tä vaa­raa ei kui­ten­kaan ole, kos­ka …Edel­li­sel­lä ri­vil­lä var­mis­tet­tiin, et­tä Q ei ole tyh­jä.

Yh­teen­las­kus­sa on vaa­ra­na, et­tä lu­ku­alue ylit­tyy. Tä­mä­kin hoi­de­taan yleen­sä muual­la kuin al­go­rit­mi­suun­nit­te­lus­sa tai jä­te­tään ko­ko­naan hoi­ta­mat­ta, vil­kai­se Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken.

Täs­sä ta­pauk­ses­sa kak­si yk­si­tyis­koh­taa kui­ten­kin kuu­luu al­go­rit­mi­suun­nit­te­lun pii­riin.

Voi­ko al­go­rit­mi yrit­tää yh­teen­las­kua si­ten, et­tä ai­na­kin toi­nen yh­teen­las­ket­ta­vis­ta on ∞? Me­hän olem­me li­sän­neet ar­von ∞ d-ken­til­le lail­lis­ten ar­vo­jen jouk­koon, jo­ten on mei­dän vas­tuul­lam­me, et­tä ∞ ei pää­dy osak­si las­ku­toi­mi­tuk­sia. Se ei pää­dy, kos­ka …Ri­veil­lä 9 ja 10 yh­teen­las­kuun osal­lis­tu­vat vain v↑d ja p. Näis­tä p on kaa­ren pi­tuus ja sik­si lu­vun 1 mu­kaan lu­ku. Myös v↑d on lu­ku, kos­ka ri­vin 5 pe­rus­teel­la v on tai on ol­lut Q:ssa, ja osoi­tim­me lu­vus­sa 3, et­tä sel­lais­ten sol­mu­jen d-ken­tät ovat lu­ku­ja. Ri­vil­lä 12 yh­teen­las­kuun osal­lis­tu­vat vain u↑d ja u↑a. Lu­vus­sa 3 to­det­tiin, et­tä ri­vin 12 alus­sa u↑d on lu­ku. (Sa­man voi pää­tel­lä sii­tä, et­tä ri­vin 10 yh­teen­las­ku on lail­li­nen.) Lu­vus­sa 2 lu­vat­tiin, et­tä myös u↑a on lu­ku. Sa­ma on­gel­ma ei kos­ke ver­taa­mis­ta ar­voon ∞ sik­si, et­tä …Lu­vus­sa 1 mää­ri­tel­tiin mi­tä se tar­koit­taa, jo­ten al­go­rit­min to­teut­ta­ja tie­tää asias­ta ja hä­nel­lä on vel­vol­li­suus to­teut­taa ver­tai­lut sen mu­kai­ses­ti. Niin­pä myös ri­vit 9, 10 ja 12 ovat kun­nos­sa.

Voi­ko d-kent­tään pää­tyä ne­ga­tii­vi­nen lu­ku, vas­toin lu­vus­sa 2 sa­not­tua? Tä­mä ei ai­heu­ta pal­joa pään­sär­kyä. Vas­tausRi­vil­lä 1 sel­väs­ti­kään ei voi. Ri­vil­lä 10 si­joi­tet­ta­va ar­vo on ei-ne­ga­tii­vis­ten lu­ku­jen sum­ma­na ei-ne­ga­tii­vi­nen. Muual­la d-kent­tien ar­vot ei­vät muu­tu.

Al­go­rit­mi py­säh­tyy

Al­go­rit­mi ei siis voi jää­dä kier­tä­mään ikui­ses­ti while-sil­muk­kaan­sa. Se ei voi jää­dä kier­tä­mään ikui­ses­ti for-sil­muk­kaan­sa­kaan, kos­ka se kier­tää ker­ral­laan vain |v↑kaaret| kier­ros­ta. Al­go­rit­mis­sa ei ole re­kur­sio­ta ei­kä muu­ta­kaan, jo­ka voi­si joh­taa päät­ty­mät­tö­mään suo­ri­tuk­seen. Olem­me to­dis­ta­neet, et­tä al­go­rit­mi py­säh­tyy var­mas­ti.

Löy­de­tyt rei­tit to­del­la ovat reit­te­jä

Seu­raa­vak­si to­dis­tam­me, et­tä seu­raa­va väi­te on ai­na voi­mas­sa:

Jo­kai­sel­le löy­ty­neel­le sol­mul­le w (eli jos w↑d ≠ ∞) on ole­mas­sa reit­ti l:stä w:hen, jon­ka pi­tuus on w↑d.

To­dis­tus koos­tuu kah­des­ta osas­ta: (1) to­dis­te­taan, et­tä väi­te on voi­mas­sa alus­sa (siis en­nen ri­vin 1 suo­ri­tus­ta), ja (2) et­tä min­kään lau­seen suo­ri­tus ei saa­ta väi­tet­tä en­sim­mäi­sen ker­ran pois voi­mas­ta. Tä­mä riit­tää, kos­ka jos ei ole en­sim­mäis­tä ker­taa jol­loin väi­te lak­kaa ole­mas­ta voi­mas­sa, niin ei voi ol­la tois­ta, kol­mat­ta ei­kä mui­ta­kaan ker­to­ja, jo­ten väi­te ei kos­kaan lak­kaa ole­mas­ta voi­mas­sa. Kos­ka osas­sa (2) pu­hu­taan en­sim­mäi­ses­tä ker­ras­ta, si­tä to­dis­tet­taes­sa saa olet­taa, et­tä väi­te oli voi­mas­sa juu­ri en­nen lau­seen suo­ri­tus­ta ja on ol­lut voi­mas­sa si­tä en­nen ko­ko ajan.

1. Nyt to­dis­tet­ta­va väi­te on voi­mas­sa alus­sa, kos­ka …Lu­vus­sa 2 il­moi­tet­tiin, et­tä alus­sa jo­kai­sel­le sol­mul­le pä­tee w↑d = ∞. Alus­sa ei siis ole löy­ty­nei­tä sol­mu­ja, jo­ten väi­te ei vel­voi­ta rei­tin ole­mas­sa­oloa mil­tään sol­mul­ta.
2. Jos lau­se ei voi muut­taa min­kään sel­lai­sen muut­tu­jan ei­kä ken­tän ar­voa, jos­ta väi­te pu­huu, niin lau­seen suo­ri­tus ei voi saat­taa väi­tet­tä pois voi­mas­ta. Sik­si kan­nat­taa tun­nis­taa ne muut­tu­jat ja ken­tät, jois­ta väi­te pu­huu. Nyt to­dis­tet­ta­van väit­teen ta­pauk­ses­sa ne ovat …Muut­tu­ja l ja kent­tä d nä­ky­vät suo­raan väit­tees­tä. Koh­ta ”on ole­mas­sa reit­ti” pu­huu kaaret-kent­tien ar­vois­ta. Vas­tauk­seen ei kuu­lu w, kos­ka w ei ole al­go­rit­min muut­tu­ja vaan väit­teen il­mai­se­mi­ses­sa käy­tet­ty ti­la­päi­nen apu­vä­li­ne.

   Mit­kä ri­vit voi­vat muut­taa nii­den ar­voa? Vas­tausl:n ja kaaret-kent­tien ar­vo­ja ei muu­ta mi­kään ri­vi. d-ken­tät voi­vat muut­tua ri­veil­lä 1 ja 10. Näis­tä en­sim­mäi­sen suo­ri­tus ei voi rik­koa väi­tet­tä, kos­ka …Sol­mus­ta l pää­see it­seen­sä py­sy­mäl­lä pai­kal­laan eli kul­ke­mal­la reit­ti, jon­ka pi­tuus on 0. Ri­vil­lä 1 ase­te­taan l↑d sen mu­kai­ses­ti. Sik­si väi­te on voi­mas­sa l:lle ri­vin 1 lo­pus­sa. Mui­den sol­mu­jen osal­ta väi­te säi­lyy voi­mas­sa, kos­ka ri­vi 1 ei muu­ta mi­tään nii­den kan­nal­ta. Jäl­kim­mäi­sen­kään suo­ri­tus ei voi rik­koa väi­tet­tä, kos­ka …Ri­vin 5 pe­rus­teel­la v on ol­lut Q:ssa, jo­ten lu­vus­sa 3 to­dis­te­tun väit­teen pe­rus­teel­la v↑d ≠ ∞. Edel­lä an­net­tiin lu­pa olet­taa, et­tä to­dis­tet­ta­va väi­te pä­ti ri­vin 10 alus­sa. Saam­me sii­tä, et­tä v↑d on jon­kin l:stä v:hen vie­vän rei­tin pi­tuus. Kun tä­män rei­tin pe­rään li­sä­tään ri­vil­lä 8 tar­kas­tel­ta­vak­si otet­tu v:stä u:hun vie­vä kaa­ri, saa­daan reit­ti l:stä u:hun, jon­ka pi­tuus on v↑d + p. Kos­ka juu­ri tä­mä ar­vo si­joi­te­taan u↑d:hen ri­vil­lä 10, on u↑d:n ar­vo ri­vin 10 lo­pus­sa jon­kin l:stä u:hun vie­vän rei­tin pi­tuus. Sik­si väi­te on voi­mas­sa u:lle ri­vin 10 lo­pus­sa. Mui­den sol­mu­jen osal­ta väi­te säi­lyy voi­mas­sa, kos­ka ri­vi 10 ei muu­ta mi­tään nii­den kan­nal­ta.

In­va­riant­ti tar­koit­taa väi­tet­tä, jo­ka voi­daan to­dis­taa täl­lä kak­si­osai­sel­la ta­val­la. Edel­lä to­dis­ta­mam­me väi­te on siis in­va­riant­ti. Usein in­va­rian­tin lu­va­taan ole­van voi­mas­sa vain jos­sa­kin tie­tys­sä koh­das­sa oh­jel­maa (esi­mer­kik­si ai­na ri­vin 4 alus­sa), mut­ta täl­lä ker­taa sen lu­va­taan ole­van voi­mas­sa jo­ka koh­das­sa.

Jos reit­te­jä on, al­go­rit­mi löy­tää jon­kin

Al­go­rit­min löy­tä­mä reit­ti on kir­jat­tu ta­ka­pe­rin e-kent­tiin. Toi­sin sa­noen, m↑e ker­too rei­tin toi­sek­si vii­mei­sen sol­mun, sen e-kent­tä ker­too rei­tin kol­man­nek­si vii­mei­sen sol­mun ja niin edel­leen läh­tö­sol­muun saak­ka. Ta­ka­pe­rin ole­van rei­tin kään­tä­mi­nen oi­kein­päin ei ole työ­läs­tä, mut­ta vie­lä hel­pom­paa on vält­tää se ko­ko­naan. Se on­nis­tuu yk­sin­ker­tai­sel­la ki­kal­la, jo­ka on …Esi­te­tään kaa­ret kar­tas­sa ta­ka­pe­rin, ja et­si­tään reit­ti maa­lis­ta läh­töön.

Läh­tö­sol­mun e-ken­tän ar­voa ei ole ase­tet­tu, jo­ten löy­det­tyä reit­tiä jäl­ki­kä­sit­te­le­vän sil­mu­kan lop­pu­eh­to­na on ol­ta­va, et­tä ny­kyi­nen sol­mu on l, ei­kä et­tä e-ken­tän ar­vo on osoi­tin ei min­ne­kään. Jos tä­mä ei ole si­nus­ta hy­vä, li­sää al­go­rit­miin si­joi­tus l↑e := osoi­tin ei min­ne­kään.

Löy­det­ty reit­ti on mah­dol­li­sim­man ly­hyt

Vie­lä täy­tyy to­dis­taa, et­tä al­go­rit­min löy­tä­mä reit­ti on niin ly­hyt kuin mah­dol­lis­ta. Si­tä var­ten on pu­hut­ta­va a-kent­tien ar­vois­ta. Al­go­rit­min toi­min­ta pe­rus­tuu ole­tuk­seen, et­tä ne nou­dat­ta­vat seu­raa­vaa eh­toa jo­kai­sel­le sol­mul­le u ja v:

Jos (u, p) ∈ v↑kaaret, niin v↑a ≤ p + u↑a.

Toi­sin sa­noen, jos sol­mus­ta v on kaa­ri sol­muun u, niin v:n ar­vioi­tu mat­ka maa­liin saa ol­la kor­kein­taan yh­tä pit­kä kuin on mat­ka v:stä u:hun jat­ket­tu­na ar­vioi­dul­la mat­kal­la u:sta maa­liin. Tä­män eh­don oi­keu­tus on kah­des­sa sei­kas­sa:

• Ku­ten myö­hem­min näh­dään, se ta­kaa, et­tä al­go­rit­mi löy­tää mah­dol­li­sim­man ly­hyen rei­tin läh­dös­tä maa­liin.
• Käyt­tö­kel­poi­sia ar­vioi­ta on ole­mas­sa.

Hy­vin help­po käyt­tö­kel­poi­nen ar­vio on va­li­ta v↑a = 0 jo­kai­sel­le sol­mul­le v. Se täyt­tää edel­lä mai­ni­tun eh­don, kos­ka …eh­to pel­kis­tyy muo­toon 0 ≤ p + 0 eli p ≥ 0, jo­ka to­teu­tuu, kos­ka lu­vus­sa 1 il­moi­tet­tiin, et­tä kaar­ten pi­tuu­det ovat ei-ne­ga­tii­vi­sia. Täl­lä va­lin­nal­la al­go­rit­mi tun­ne­taan ni­mel­lä Dijkstran al­go­rit­mi.

Toi­nen, to­del­li­sil­le maan­tie­kar­toil­le käyt­tö­kel­poi­nen ja usein hy­vä ar­vio on lin­nun­tie-etäi­syys eli etäi­syys suo­raa vii­vaa pit­kin. Paik­ko­jen (x, y) ja (X, Y) vä­li­nen lin­nun­tie-etäi­syys voi­daan las­kea lau­sek­keel­la

√(X − x)² + (Y − y)² .

Se on ly­hin mah­dol­li­nen etäi­syys kah­den pai­kan vä­lil­lä, jos kul­ke­mi­nen sal­li­taan myös muu­ten kuin kaa­ria pit­kin. Edel­lä mai­nit­tu eh­to v↑a ≤ p + u↑a pä­tee, kos­ka …v↑a on ly­hin mah­dol­li­nen etäi­syys v:stä maa­liin, ja v:stä u:hun vie­vää kaar­ta pit­kin ja sen jäl­keen lin­nun­tie­tä u:sta maa­liin mi­tat­tu etäi­syys on jo­kin mah­dol­li­nen etäi­syys v:stä maa­liin, jo­ten jäl­kim­mäi­nen on vä­hin­tään yh­tä pit­kä kuin edel­li­nen.

Jos w on sol­mu, niin tar­koit­ta­koon δ(w) mah­dol­li­sim­man ly­hyen l:stä w:hen vie­vän rei­tin pi­tuut­ta. Jos ei ole ole­mas­sa reit­tiä l:stä w:hen, niin δ(w) = ∞. Kos­ka …lu­vus­sa 6 osoi­tet­tiin, et­tä w↑d on jon­kin l:stä w:hen vie­vän rei­tin pi­tuus tai ∞, pä­tee w↑d ≥ δ(w). Lu­vus­sa 3 to­det­tiin, et­tä w↑d ei kos­kaan kas­va. Muis­tam­me, et­tä sol­mun kä­sit­te­ly tar­koit­taa ri­vien 7, …, 12 suo­rit­ta­mis­ta sil­le.

Näil­lä eväil­lä to­dis­tam­me, et­tä seu­raa­va väi­te on al­go­rit­min in­va­riant­ti:

Jo­kai­sel­le sol­mul­le w pä­tee, et­tä jos w on kä­si­tel­ty, niin w↑d = δ(w).

Alus­sa tä­mä pä­tee, kos­ka …alus­sa mi­kään sol­mu ei ole kä­si­tel­ty. Jos w↑d = δ(w), niin w↑d:n ar­vo ei voi enää muut­tua, kos­ka …w↑d ei kos­kaan kas­va ei­kä voi ol­la pie­nem­pi kuin δ(w). Sik­si in­va­rian­tin voi­mas­sa säi­ly­mi­sen to­dis­ta­mi­sek­si riit­tää to­dis­taa, et­tä al­go­rit­mi kä­sit­te­lee ri­veil­lä 7, …, 12 vain sel­lai­sia sol­mu­ja w, joil­le w↑d = δ(w). En­nen kuin sol­mu kä­si­tel­lään, se tu­lee ulos Q:sta ri­vil­lä 5. Sik­si riit­tää to­dis­taa, et­tä mi­kään sol­mu w ei tu­le ulos Q:sta en­nen kuin w↑d on pie­nen­ty­nyt ar­voon δ(w). Teem­me tä­män to­dis­ta­mal­la seu­raa­van:

Jos suo­ri­tus on ri­vin 5 alus­sa ja w↑d ≠ δ(w), niin Q:sta seu­raa­vak­si tu­le­va sol­mu ei ole w.

En­sin osoi­tam­me, et­tä on ole­mas­sa reit­ti l:stä w:hen. Se pä­tee, kos­ka …Kos­ka w↑d ≥ δ(w) ja w↑d ≠ δ(w), pä­tee w↑d > δ(w). Kos­ka w↑d voi ol­la vain lu­ku tai ∞, sii­tä seu­raa, et­tä δ(w) < ∞ eli reit­ti on ole­mas­sa. Tä­män voi to­dis­taa myös si­ten, et­tä jos reit­tiä ei ole, niin δ(w) = ∞ ja lu­vun 6 no­jal­la w↑d = ∞, mi­kä on ris­ti­rii­das­sa ole­tuk­sen w↑d ≠ δ(w) kans­sa. Kos­ka on ole­mas­sa reit­ti (ja kos­ka kart­ta on ää­rel­li­nen kos­ka se on al­go­rit­min syö­te), on ole­mas­sa myös mah­dol­li­sim­man ly­hyt reit­ti eli sel­lai­nen, jon­ka pi­tuus on δ(w). Ol­koon t sen en­sim­mäi­nen kä­sit­te­le­mä­tön sol­mu. Sel­lai­nen on ole­mas­sa, kos­ka …Ai­na­kin w on kä­sit­te­le­mä­tön, kos­ka muu­toin in­va­rian­tin mu­kaan ole­tus w↑d ≠ δ(w) ei pä­ti­si. In­va­riant­tiin­han saa ve­do­ta ti­lan­tees­sa en­nen tut­kit­ta­vien lau­sei­den eli täs­sä ta­pauk­ses­sa ri­vien 5, …, 12 suo­ri­tus­ta.

Jos t = l, niin l on kä­sit­te­le­mät­tä, kos­ka …t va­lit­tiin si­ten, et­tä se on kä­sit­te­le­mät­tä. Niin­pä ri­vin 5 alus­sa ol­laan en­sim­mäis­tä ker­taa ja Q:sta tu­lee seu­raa­vak­si l. Se ei ole w, kos­ka …sil­loin l↑d = 0 = δ(l), mut­ta ole­tim­me, et­tä w↑d ≠ δ(w).

Muus­sa ta­pauk­ses­sa t ei ole tar­kas­tel­ta­van rei­tin en­sim­mäi­nen sol­mu. Ol­koon edel­tä­vän sol­mun ni­mi s. Se on kä­si­tel­ty, kos­ka …t on rei­tin en­sim­mäi­nen kä­sit­te­le­mä­tön sol­mu. Kos­ka s on kä­si­tel­ty, s↑d = δ(s) in­va­rian­tin vuok­si. Ol­koon p ly­him­män s:stä t:hen vie­vän kaa­ren pi­tuus. Kun s kä­si­tel­tiin, tä­mä kaa­ri tut­kit­tiin ja las­ket­tiin s↑d + p eli δ(s) + p. Kos­ka …ko. kaa­ri on osa mah­dol­li­sim­man ly­hyt­tä reit­tiä l:stä w:hen, δ(s) + p = δ(t). Sik­si vii­meis­tään sil­loin si­joi­tet­tiin t↑d:hen δ(t) ja li­sät­tiin (t, δ(t) + t↑a) Q:hun.

Kos­ka …t ei ole kä­si­tel­ty, (t, δ(t) + t↑a) on yhä Q:ssa. Ol­koon q t:stä w:hen vie­vän mah­dol­li­sim­man ly­hyen rei­tin pi­tuus. Täs­sä lu­vus­sa to­dis­ta­mam­me pe­rus­teel­la t↑a ≤ q + w↑a. Sii­tä seu­raa δ(t) + t↑a ≤ δ(t) + q + w↑a = δ(t) + q = δ(w), kos­ka ol­laan mah­dol­li­sim­man ly­hyel­lä rei­til­lä l:stä w:hen.δ(w) + w↑a. Saim­me δ(w) + w↑a ≥ δ(t) + t↑a. Jos (w, x) on Q:ssa, niin x ≥ Kun (w, x) li­sät­tiin Q:hun pä­ti x = w↑d + w↑a. Sen jäl­keen w↑a ei ole muut­tu­nut ja w↑d on voi­nut pie­nen­tyä tai py­syä en­nal­laan, mut­ta ei ole kas­va­nut.w↑d + w↑a > Ole­tim­me w↑d ≠ δ(w), ja näim­me jo aiem­min et­tä sii­tä seu­raa w↑d > δ(w).δ(w) + w↑a ≥ δ(t) + t↑a. Sik­si δ(t) + t↑a < x, jo­ten t tu­lee Q:sta en­nen w:tä.

Sik­si al­go­rit­min löy­tä­mät rei­tit ovat mah­dol­li­sim­man ly­hyi­tä.

To­teu­tus­yk­si­tyis­koh­dis­ta

Prio­ri­teet­ti­jo­non Q to­teu­tus on kriit­ti­nen al­go­rit­min no­peu­den kan­nal­ta. On­gel­ma­na on to­teut­taa se si­ten, et­tä se­kä li­säys et­tä en­sim­mäi­sen pois­ta­mi­nen ta­pah­tu­vat no­peas­ti. Tä­hän tar­koi­tuk­seen so­pii hy­vin tie­to­ra­ken­ne, jo­ka tun­ne­taan ni­mel­lä ke­ko. Sen avul­la se­kä li­säys et­tä pois­to on­nis­tu­vat ajas­sa log |Q|.

Muut al­go­rit­min ope­raa­tiot kuin Q:hun li­sää­mi­nen ja pois­to on help­po to­teut­taa va­kio­ai­kai­si­na. To­del­li­ses­sa to­teu­tuk­ses­sa k- ja d-ken­tät on alus­tet­ta­va en­nen ri­viä 1, mis­tä tu­lee suo­ri­tus­ai­kaan kom­po­nent­ti O(|V|). Ri­vit 9, …, 12 suo­ri­te­taan kor­kein­taan ker­ran jo­kais­ta kaar­ta koh­den, jo­ten keon kook­si voi tul­la kor­kein­taan |E|. Mi­tään ri­viä ei suo­ri­te­ta useam­min kuin |E| + 1 ker­taa, jo­ten ke­koa käyt­täen al­go­rit­min suo­ri­tus­ai­ka on O(|V| + |E| log |E|).

Suo­ri­tus­ai­ka on lä­hel­lä tä­tä ylä­ra­jaa esi­mer­kik­si sil­loin, kun kaik­ki ne kaa­ret, jot­ka ei­vät ole ly­him­mäl­lä rei­til­lä läh­dös­tä maa­liin, al­ka­vat läh­dös­tä, ovat kes­ke­nään eri­pi­tui­sia ja pi­tem­piä kuin ly­hin reit­ti läh­dös­tä maa­liin, ja läh­dös­tä al­ka­vat kaa­ret tu­le­vat syöt­tees­sä vas­taan pi­tuus­jär­jes­tyk­ses­sä pi­sin en­sin. Täs­sä ta­pauk­ses­sa jo­kai­nen hyö­dy­tön kaa­ri tuot­taa he­ti alus­sa Q:hun al­kion, jo­ka py­syy siel­lä kun­nes maa­li on löy­ty­nyt.

Sa­ma sol­mu voi ol­la Q:ssa sa­man­ai­kai­ses­ti useaan ker­taan. Näis­tä vain se esiin­ty­mä on hyö­dyl­li­nen, jo­hon liit­ty­vä lu­ku on pie­nin. Jos esiin­ty­mät pois­tet­tai­siin si­tä mu­kaa kuin ne käy­vät hyö­dyt­tö­mik­si, Q ei kos­kaan kas­vai­si suu­rem­mak­si kuin |V|. Keol­la tä­mä on han­ka­laa, kos­ka ta­val­li­ses­ta keos­ta on han­ka­laa löy­tää muu­ta al­kio­ta kuin prio­ri­tee­tis­sa en­sim­mäi­se­nä ole­va. On­gel­ma on kui­ten­kin rat­kais­ta­vis­sa, jol­loin pääs­tään suo­ri­tus­ai­kaan O(|V| + |E| log |V|). On myös ole­mas­sa mo­ni­mut­kai­sem­pi tie­to­ra­ken­ne, jol­la pääs­tään vie­lä pa­rem­paan suo­ri­tus­ai­kaan O(|E| + |V| log |V|). Näit­ten pa­ran­nus­ten hyö­ty on ta­val­li­sen maan­tie­kar­tan ta­pauk­ses­sa ky­seen­alai­nen, kos­ka sa­maan ris­teyk­seen tu­lee har­voin ko­vin mon­taa tie­tä, jo­ten |V| + |E| log |E| ei ole ko­vin pal­jon suu­rem­pi kuin |E| + |V| log |V|. Muis­sa so­vel­luk­sis­sa ti­lan­ne voi ol­la toi­nen.

Al­go­rit­mi kä­sit­te­lee maa­lin tur­haan (pait­si jos se on sa­ma kuin läh­tö). Se väl­tet­täi­siin, jos ri­vil­lä 4 ole­van osa­tes­tin v ≠ m si­jaan ri­vien 5 ja 6 vä­lis­sä tes­tat­tai­siin on­ko v = m ja jos vas­taus on kyl­lä, niin hy­pät­täi­siin pois sil­mu­kas­ta. Pseu­do­koo­diin si­tä ei kir­joi­tet­tu niin, jot­ta ei oli­si tar­vin­nut esi­tel­lä mer­kin­tää, jol­la sil­mu­kas­ta hy­pä­tään pois kes­kel­tä.