Trumpiausių kelių algoritmų taikymo sąlygos
Briaunų svoriai lemia, kuris trumpiausių kelių metodas tinka.
Esminės žinios
BFS randa trumpiausius kelius nesvertiniame grafe, kai jų ilgis matuojamas briaunų skaičiumi. Dijkstros algoritmas apskaičiuoja mažiausio svorio atstumus iš vienos pradinės viršūnės, kai visų briaunų svoriai yra neneigiami, kiekviename žingsnyje galutinai nustatydamas mažiausią preliminarų atstumą.
Sąlygos ir taikymo ribos
- Grafas yra baigtinis, o pradinė viršūnė nurodyta; nepasiekiamų viršūnių atstumas yra begalinis.
- Esant neigiamiems briaunų svoriams, bendroji Dijkstros algoritmo garantija nebegalioja; kelio svoris apskaičiuojamas sudedant jo briaunų svorius.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
Pagrindimas ir peržiūra
Grafų apibrėžimai, gretimumo vaizdavimo būdai, briaunų skaičiumi matuojami atstumai ir BFS trumpiausi keliai. Neneigiamų briaunų svorių prielaida, monotoniški trumpiausių kelių atstumai ir Dijkstros algoritmas.
2026-10-10 · Paieška į plotį (BFS) nesvertiniuose grafuose ir Deikstros algoritmas grafuose su neneigiamais svoriais, neįtraukiant algoritmų, leidžiančių neigiamų svorių briaunas be apribojimų.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-shortest-paths
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas