Bellmano–Fordo algoritmas ir neigiami ciklai
Pradžioje nustatoma d(s)=0, o kiti atstumai prilyginami begalybei; tada kiekviena orientuota briauna relaksuojama per |V|−1 iteracijų.
Esminės žinios
Pradžioje nustatoma d(s)=0, o kiti atstumai prilyginami begalybei; tada kiekviena orientuota briauna relaksuojama per |V|−1 iteracijų. Atstumai yra teisingi, kai nėra pasiekiamo neigiamo ciklo; atstumo sumažėjimas per dar vieną iteraciją liudija, kad yra pasiekiamas neigiamas ciklas. Reikia O(|V||E|) relaksacijų ir pradinių reikšmių nustatymo.
Sąlygos ir taikymo ribos
- Briaunų svoriai gali būti neigiami.
- Viršūnėms, pasiekiamoms iš pasiekiamo neigiamo ciklo, neegzistuoja baigtinis trumpiausio maršruto svoris; nepasiekiami neigiami ciklai neturi įtakos pradinei viršūnei.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitoje 12 aptariami paprastieji trumpiausi keliai, |V| briaunų liudijantis maršrutas ir įprasta relaksacija.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-bellman-ford
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra