Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Dijkstra keon avulla

Greedy-lyhimmät polut epänegatiivisilla kaarilla

Oppitunti 1/413 vaihetta

Dijkstra keon avulla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Lyhimmän polun ongelma

Haluatte löytää edullisimman reitin yhdestä solmusta kaikkiin muihin solmuihin. Dijkstra ratkaisee tämän, kun kaikkien kaarten painot ovat nollia tai positiivisia.

Ahne idea

Dijkstra on ahne: se laajentaa aina käymättömän solmun, jonka tunnettu etäisyys on pienin, ja luottaa siihen, että etäisyys on lopullinen.

Miksi minimikeko tarvitaan

Lähimmän solmun hakemiseen nopeasti tarvitaan minimikeko. Se antaa pienimmän etäisyyden ajassa log n sen sijaan, että kaikki vaihtoehdot jouduttaisiin käymään hitaasti läpi.

import heapq

Aloittakaa etäisyyksistä

Asettakaa kaikki etäisyydet arvoon ääretön ja asettakaa lähdesolmun etäisyydeksi nolla. Saavuttamattomat solmut jäävät yksinkertaisesti ikuisesti arvoon ääretön.

dist = [float('inf')] * n
dist[src] = 0

Alustakaa keko

Lisätkää lähdesolmu kekoon tuple-rakenteena (etäisyys, solmu). Kun etäisyys on ensimmäisenä, keko järjestää alkiot automaattisesti kustannuksen mukaan.

pq = [(0, src)]

Poimikaa lähin solmu

Poimikaa jokaisella kierroksella pop-toiminnolla pienin alkio (d, u). Tällöin d on solmun u lyhin etäisyys, joten sen käsittely on valmis.

d, u = heapq.heappop(pq)

Ohittakaa vanhentuneet alkiot

Solmu voi olla keossa vanhalla ja liian suurella etäisyydellä. Ohittakaa alkio, kun d on suurempi kuin tallennettu etäisyys.

if d > dist[u]:
    continue

Relaksoikaa naapurit

Relaksaatio tarkoittaa naapurin etäisyyden parantamisen yrittämistä: jos kulkeminen solmun u kautta on halvempaa, päivittäkää etäisyys ja lisätkää naapuri kekoon.

if d + w < dist[v]:
    dist[v] = d + w
    heapq.heappush(pq, (dist[v], v))

Laiskan poiston temppu

Pythonin keot eivät voi päivittää avainta, joten lisäätte keon uusia kopioita ja ohitatte vanhentuneet alkiot. Tämä laiska tyyli pitää koodin lyhyenä ja nopeana.

Suoritusaika

Binaarikeolla Dijkstran algoritmi toimii ajassa O((V + E) log V). Se käsittelee helposti graafeja, joissa on satojatuhansia kaaria.

Huomioikaa kaarten painot

Dijkstra ei toimi negatiivisten kaarten kanssa, koska poimittu etäisyys ei välttämättä ole lopullinen. Käyttäkää tällöin Bellman-Fordia.

Pikatarkistus

Poimitte alkion (d, u), mutta d on suurempi kuin dist[u]. Mitä pitäisi tehdä?

Vastaa interaktiivisessa oppitunnissa

Kertaus: Dijkstra keon avulla

Alustatte etäisyydet, lisäätte kekoon parit (dist, node), poimitte lähimmän alkion, ohitatte vanhentuneet poiminnat ja relaksoitte naapurit. Tämä on Dijkstra ajassa O((V+E) log V). 🚀

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Dijkstra keon avulla” ilmainen?

Kyllä – oppitunnin ”Dijkstra keon avulla” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Dijkstra keon avulla”?

Greedy-lyhimmät polut epänegatiivisilla kaarilla Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.

Kuinka kauan ”Dijkstra keon avulla”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin