Trumpiausio kelio algoritmo užduoties sprendimas. Belmano – Fordo algoritmas

Trumpiausio kelio algoritmo užduoties sprendimas

Belmano – Fordo algoritmas

Pasirinkite algortimą ir eksperimento būtų nustatykite jo sudėtingumą. Fiksuokite grafo viršūnių skaičių ir didinkite tik briaunų skaičių.

Jūsų pasirinkti: Belmano ir Fordo algoritmas

Belmano - Fordo algoritmas

Trumpiausio kelio uždaviniai sprendžiami, ieškant trumpiausio kelio tarp dviejų grafo viršūnių (arba tinklo mazgų). Kelio ilgis priklauso nuo jį sudarančių atkarpų reikšmių sumos. Mažiausia kelio ilgio reikšmė ir yra trumpiausias kelias. Belmano - Fordo algoritmas yra vienas iš trumpiausio kelio algoritmų pavyzdžių. Minėtas algoritmas apibūdinamas, kaip randantis kelius ir tuose grafuose, kur briaunos svoris gali būti neigiamas.

Į algoritmo programą briaunų skaičius įvedamas iš klaviatūros. Briaunų skaičius didinamas nuo 1000 iki 10000. Viršūnių skaičius fiksuotas, šiuo atveju, 10. Rikiavimo laikas matuojamas mikrosekundėmis.

Rezultatai pateikiami lentelėje

Rezultatai pateikiami diagramoje

Išvados

1. Remiantis teorija, Belmano - Fordo algoritmo sudėtingumas yra O(VE), kur V yra grafo viršūnių skaičius, o E yra briaunų skaičius. Šis algoritmas yra naudojamas trumpiausio kelio paieškai tarp visų porų viršūnių grafe, net jei yra neigiamos briaunos. Todėl šio konkretaus algoritmo sudėtingumas yra O(VE).

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!