Mitu erinevat topoloogilist järjestust on graafil

Märgi alljärgnevatest kõik suunatud graafide liigid, mille tipud saab alati

topoloogiliselt järjestada.

Eelnevas vaatlesime kolme algoritmi lühimate teede leidmiseks. Üldiselt võib algoritme jaotada klassidesse olenevalt nende aluseks olevast strateegiast. Levinumad algoritmides kasutatavad strateegiad on järgmised.

• Ahne algoritm
• Tagasipöördumisega otsing
• Harude ja tõkete meetod
• Dünaamiline planeerimine
• Täielik läbivaatus
• Jaga ja valitse

Mis strateegiaid kasutavad vaadeldud lühima tee algoritmid?

Olgu Floydi-Warshalli algoritm realiseeritud nagu eelnevas, st tsüklid

on üle indeksite

Märgi kõik laused, mis on kauguste maatriksi d elementide kohta kindlasti tõesed.

Mis näitab Bellmani-Fordi algoritmis, et graafis, kus on V tippu, leidub

negatiivse pikkusega tsükkel?

Kaugus tähendab siin tipu jooksvat kaugust, nagu seda algoritm arvutab.