Kai briaunos nustoja būti vienodos

Keturiolikta pamoka baigėsi taip:

BFS atsako „per kiek perėjimų", nes kiekvienas perėjimas kainuoja tiek pat. Laiko išplėstiniame grafe jie kainuoja skirtingai — ir BFS tai ignoruoja.

Dabar tavo bibliotekos tinklo briaunos irgi turi kainą: dienas tarp skolinimų. Skaitytojas vieną knygą pasiėmė po trijų dienų, kitą — po penkių savaičių.

Klausimas pasikeitė. Ne „per kiek knygų", o „per kiek dienų".

$ algo route
nodes 1000, edges 742, weights = days between borrows (1..60)
route from 0 to 194

                                 hops       days
  BFS (fewest hops)                12        402
  Dijkstra (fewest days)           12        191

  the cheapest route takes 0 more hops and saves 211 days

Tas pats perėjimų skaičius. Dvigubai skirtingas atsakymas.

Abu keliai turi po 12 briaunų, tad BFS jų neatskirtų — jai jie vienodi. Bet vienas trunka 402 dienas, o kitas 191.

Ir tai ne kraštinis atvejis. Iš 561 pasiekiamos knygos BFS pasirinktas kelias skiriasi nuo pigiausio 197 kartus (35.1 %).

Ko tam reikia

Dijkstros algoritmas kiekviename žingsnyje klausia: kuris dar neapdorotas mazgas yra pigiausias?

Šis klausimas tau pažįstamas. Tryliktoje pamokoje pastatei struktūrą, kuri atsako į jį per O(log n) ir kurios minimumas yra a[0].

Nauja struktūra šioje pamokoje nestatoma. Statoma paieška, kuriai ta struktūra buvo skirta nuo pat pradžių.

Spėk prieš skaitydamas toliau

Krūvą galima ir nenaudoti. Vietoj jos kiekviename žingsnyje galima peržiūrėti visus mazgus ir pasiimti mažiausią — O(V) vietoj O(log V). Atsakymas bus tas pats; skirsis tik greitis.

Pirmoje pamokoje pasirinktas prietaisas buvo operacijų skaitiklis, ne laikrodis — nes skaitiklis nepriklauso nuo mašinos.

Kiek kartų daugiau darbo atliks tiesinė versija? Ir kiek kartų ilgiau truks? Ar tie du skaičiai sutaps?

Užsirašyk abu. Penktame žingsnyje pamatuosi, ir jie nesutaps — o kodėl, yra šeštas kartas, kai šiame kurse tai atsitinka.