[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bellman-ford-algorytm-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bellman-ford-algorytm-wikipedia\/","headline":"Bellman-Ford Algorytm-Wikipedia","name":"Bellman-Ford Algorytm-Wikipedia","description":"before-content-x4 L ‘ Algorytm Bellman-Ford , nazywane r\u00f3wnie\u017c Bellman – Ford – Algorytm Moore [[[ 3 ] , jest algorytmem,","datePublished":"2021-12-02","dateModified":"2021-12-02","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/34c94109b6b9bb8a46b559cbadc2375af6465bf9","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/34c94109b6b9bb8a46b559cbadc2375af6465bf9","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bellman-ford-algorytm-wikipedia\/","wordCount":12568,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4L ‘ Algorytm Bellman-Ford , nazywane r\u00f3wnie\u017c Bellman – Ford – Algorytm Moore [[[ 3 ] , jest algorytmem, kt\u00f3ry oblicza najkr\u00f3tsze \u015bcie\u017cki z danego szczytu \u017ar\u00f3d\u0142owego na wa\u017conym wykresie zorientowanym. Nosi nazw\u0119 swoich wynalazc\u00f3w Richard Bellman i Lester Randolph Ford Junior (publikacje w 1956 i 1958 r.) Oraz Edwarda Forresta Moore’a, kt\u00f3ry odkry\u0142 go na nowo w 1959 roku.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4W przeciwie\u0144stwie do algorytmu Dijkstra, algorytm Bellmana-Ford zezwala na obecno\u015b\u0107 niekt\u00f3rych negatywnych \u0142uk\u00f3w wagowych i umo\u017cliwia wykrycie istnienia obwodu ch\u0142onnego, to znaczy o \u015bci\u015ble ujemnej ca\u0142kowitej wadze, dost\u0119pnej ze szczytu \u017ar\u00f3d\u0142owego. Z\u0142o\u017cono\u015b\u0107 algorytmu jest w O ( |. S |. |. A |. ) {DisplayStyle o (| s || a |)} Lub        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4|. S |. {DisplayStyle | s |} to liczba szczyt\u00f3w |. A |. {displayStyle | a |} to liczba \u0142uk\u00f3w.   Oblicza si\u0119 algorytm Bellman-Ford, bior\u0105c pod uwag\u0119 wykres        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4G = ( S W A ) {DisplayStyle g = (s, a)} Bez ujemnego cyklu masy i szczytu \u017ar\u00f3d\u0142owego S \u2208 S {DisplayStyle sin s} , kr\u00f3tsza \u015bcie\u017cka S {DisplayStyle s} Na ka\u017cdym szczycie G {DisplayStyle g} . Pozwala tak\u017ce takiej \u015bcie\u017cki na znalezienie poprzednik\u00f3w ka\u017cdego szczytu na takiej \u015bcie\u017cce. Ponadto umo\u017cliwia wykrycie przypadk\u00f3w, w kt\u00f3rych wyst\u0119puje ujemny cykl masy, a zatem, w kt\u00f3rych niekoniecznie jest kr\u00f3tszy mi\u0119dzy dwoma szczytami. Algorytm wykorzystuje zasad\u0119 dynamicznego programowania (jest on traktowany w rozdziale na temat programowania dynamicznego w niekt\u00f3rych ksi\u0105\u017ckach algorytmicznych [[[ 4 ] ). Sub-problublicms to: D [[[ T W k ] {DisplayStyle d [t, k]} jest odleg\u0142o\u015bci\u0105 od \u017ar\u00f3d\u0142a S do T do T ze \u015bcie\u017ck\u0105 zawieraj\u0105c\u0105 co najwi\u0119cej K \u0142uk\u00f3w. Na : D [[[ T W 0 ] = + \u221e {DisplayStyle d [t, 0] =+infty} Dla T \u2260 S {DisplayStyle tneq s} I D [[[ S W 0 ] = 0 {DisplayStyle d [s, 0] = 0} ; D [[[ T W k ] = M I N [[[ d[t,k\u22121],minarc\u00a0(u,t)(d[u,k\u22121]+poids(u,t))] {DisplayStyle d [t, k] = minleft [d [t, k-1], min _ {{text {arc}} (u, t)} (d [u, k-1]+poids (u, t) )Prawid\u0142owy]} . Algorytm oblicza warto\u015bci D [[[ T W k ] {DisplayStyle d [t, k]} wed\u0142ug warto\u015bci wzrostu k. Odleg\u0142o\u015b\u0107 od S do T jest D [[[ T W |. S |. – Pierwszy ] {DisplayStyle d [t, | s | -1]} . Algorytm Bellman-Ford jest zatem pisany przy u\u017cyciu danej relacji nawrot\u00f3w bezpo\u015brednio w poprzednim rozdziale [[[ 5 ] .  funkcjonowa\u0107 Bellman-Ford (G = (S, A), Poids, S) Dla W W S DO ZROBIENIA |. d [u] = +\u221e   |. pred [u] = null   d [s] = 0   \/\/ G\u0142\u00f3wna p\u0119tla  Dla k = 1 dop\u00f3ki Rozmiar (y) - 1 DO ZROBIENIA |. dla ka\u017cdego Arc (u, v) wykresu DO ZROBIENIA |. |. I d [u] + poids (u, v)  d [u] + poids (u, v) WI\u0118C |. Poka\u017c \u201eIstnieje cykl ch\u0142onny\u201d Z\u0142o\u017cono\u015b\u0107 algorytmu jest w O ( |. S |. |. A |. ) {DisplayStyle o (| s || a |)} Lub |. S |. {DisplayStyle | s |} to liczba szczyt\u00f3w i |. A |. {displayStyle | a |} to liczba \u0142uk\u00f3w. Odpowiada to z\u0142o\u017cono\u015bci w O ( |. S |. 3 ) {DisplayStyle o (| s |^{3})} Dla prostego g\u0119stego wykresu [[[ 5 ] . Demonstracj\u0119 korekcji algorytmu mo\u017cna wykona\u0107 przez nawr\u00f3t: Lemme. Po I {DisplayStyle i} Pr\u00f3by g\u0142\u00f3wnej p\u0119tli: Dow\u00f3d. W sprawie I = 0 {DisplayStyle i = 0} , odpowiadaj\u0105cy pierwszemu wykonaniu p\u0119tli Do , z jednej strony, D [[[ S ] = 0 {DisplayStyle d [s] = 0} I na ka\u017cdy szczyt W \u2260 S {DisplayStyle Uneq s} W D [[[ W ] = + \u221e {DisplayStyle d [u] =+infty} , udowodnienie pierwszego punktu, a z drugiej strony, S {DisplayStyle s} jest jedynym szczytem, \u200b\u200bponiewa\u017c jest \u015bcie\u017cka co najwy\u017cej 0 kraw\u0119dzi \u0142\u0105cz\u0105cego j\u0105 S {DisplayStyle s} . W sprawie I {DisplayStyle i} Nie nikogo: Z jednej strony, za\u0142\u00f3\u017cmy D [[[ W ] {DisplayStyle d [v]} by\u0107 aktualizowane D [[[ W ] : = D [[[ W ] + waga ( W W W ) {DisplayStyle d [v]: = d [u]+{text {poids}} (u, v)} . Nast\u0119pnie jako D [[[ W ] \u2260 + \u221e {DisplayStyle d [u] neq +infty} (Poniewa\u017c w przeciwnym razie aktualizacja nie mia\u0142aby miejsca), D [[[ W ] {DisplayStyle d [u]} reprezentuje ci\u0119\u017car \u015bcie\u017cki S {DisplayStyle s} ma W {displayStyle u} . Dlatego przez budow\u0119, D [[[ W ] {DisplayStyle d [v]} to waga \u015bcie\u017cki S {DisplayStyle s} ma W {DisplayStyle v} ; Z drugiej strony lub C {DisplayStyle C} , kr\u00f3tsza \u015bcie\u017cka S {DisplayStyle s} ma W {DisplayStyle v} Od najbardziej I {DisplayStyle i} ko\u015bci. Albo W {displayStyle u} Ostatni szczyt wcze\u015bniej W {DisplayStyle v} na tej \u015bcie\u017cce. Albo C \u2032 {DisplayStyle C ‘} , Sideland of C {DisplayStyle C} z S {DisplayStyle s} ma W {displayStyle u} . Nast\u0119pnie przez indukcj\u0119, C \u2032 {DisplayStyle C ‘} jest kr\u00f3tsz\u0105 \u015bcie\u017ck\u0105 S {DisplayStyle s} ma W {displayStyle u} Od najbardziej I – Pierwszy {DisplayStyle I-1} kraw\u0119dzie (w rzeczywisto\u015bci, je\u015bli nie, istnieje \u015bci\u015ble kr\u00f3tsza \u015bcie\u017cka S {DisplayStyle s} ma W {displayStyle u} . Dodaj\u0105c kraw\u0119d\u017a W {displayStyle u} ma W {DisplayStyle v} , istnieje \u015bcie\u017cka \u015bci\u015ble ni\u017csza ni\u017c C {DisplayStyle C} z S {DisplayStyle s} ma W {DisplayStyle v} , co jest sprzeczne z definicj\u0105 C {DisplayStyle C} ). Nast\u0119pnie, przez hipotez\u0119 nawrot\u00f3w, po iteracji I – Pierwszy {DisplayStyle I-1} W D [[[ W ] {DisplayStyle d [u]} by\u0142 co najwy\u017cej d\u0142ugo\u015bci kr\u00f3tszej \u015bcie\u017cki S {DisplayStyle s} ma W {displayStyle u} Od najbardziej I – Pierwszy {DisplayStyle I-1} ko\u015bci. Tak wi\u0119c w I {DisplayStyle i} -Me iteracja, D [[[ W ] \u2264 D [[[ W ] + waga ( W W W ) {DisplayStyle d [v] leq d [u]+{text {poids}} (u, v)} , ze wzgl\u0119du na struktur\u0119 algorytmu. Jednak ta ostatnia d\u0142ugo\u015b\u0107 jest co najwy\u017cej d\u0142ugo\u015bci kr\u00f3tszej \u015bcie\u017cki S {DisplayStyle s} ma W {DisplayStyle v} . Dlatego wykazano lemat. Wynika z tego, \u017ce d\u0142ugo\u015b\u0107 D [[[ W ] {DisplayStyle d [u]} jest d\u0142ugo\u015bci\u0105 kr\u00f3tszej \u015bcie\u017cki S {DisplayStyle s} ma W {displayStyle u} , co dowodzi korekcj\u0105 algorytmu Bellman-Ford w przypadku tego G {DisplayStyle g} nie ma ujemnego cyklu masy [[[ 5 ] . Wykonanie g\u0142\u00f3wnej p\u0119tli mo\u017cna zatrzyma\u0107, gdy odleg\u0142o\u015bci pozostan\u0105 niezmienione. Cia\u0142o g\u0142\u00f3wnej p\u0119tli jest nast\u0119pnie wykonywane mniej ni\u017c |. S |. – Pierwszy {DisplayStyle | s | -1} czasy. Z\u0142o\u017cono\u015b\u0107 w najgorszym przypadku jest niezmieniona. Jen [[[ 6 ] opisa\u0142 dwie ulepszenia algorytmu Bellman-Ford, kt\u00f3re nie zmieniaj\u0105 z\u0142o\u017cono\u015bci w najgorszym przypadku, ale co sprawia, \u017ce \u200b\u200bjest szybszy w praktyce. Pierwsza poprawa zmniejsza liczb\u0119 relaksu. Je\u015bli d [u] nie zosta\u0142 zmodyfikowany od czasu relaksacji \u0142uku (u, t), nie ma potrzeby uwalniania \u0142uk\u00f3w (u, t) po raz drugi. Zatem, wraz ze wzrostem liczby szczyt\u00f3w o prawid\u0142owej odleg\u0142o\u015bci podczas algorytmu, liczba \u0142uk\u00f3w, kt\u00f3re zostan\u0105 uwolnione z ka\u017cdej iteracji. Zarabiamy sta\u0142\u0105 czynnik z\u0142o\u017cono\u015bci g\u0119stych wykres\u00f3w. Drugim ulepszeniem Yena jest wybranie dowolnego ca\u0142kowitego zam\u00f3wienia      (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2pl\/wiki27\/bellman-ford-algorytm-wikipedia\/#breadcrumbitem","name":"Bellman-Ford Algorytm-Wikipedia"}}]}]