Bellman-Ford-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20. helmikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .

Bellman-Ford-algoritmi

Nimetty	Richard Bellman ja Ford, Lester
Tekijä	Richard Bellman , Ford, Lester ja Edward Forest Moore
tarkoitus	lyhimmän polun löytäminen kaaviosta
Tietorakenne	kaavio
pahin aika	$\Theta (\|V\|\|E\|)$
Paras aika	$\Theta (\|E\|)$
Muistin hinta	$\Theta (\|V\|)$
Mediatiedostot Wikimedia Commonsissa

Bellman-Ford- algoritmi on algoritmi lyhimmän polun löytämiseksi painotetusta kuvaajasta . Ajan myötä algoritmi löytää lyhyimmät polut graafin yhdestä kärjestä kaikkiin muihin. Toisin kuin Dijkstran algoritmi, Bellman-Ford-algoritmi sallii reunat negatiivisilla painoilla . Richard Bellman ja Lester Ford ehdottivat itsenäisesti . Siriuksen suosima. $O(|V|\cdot |E|)$

RIP - reititysalgoritmi (Bellman-Ford-algoritmi) kehitettiin ensimmäisen kerran vuonna 1969 ARPANETin perustaksi .

Ongelman kuvaus

Annettu suunnattu tai suuntaamaton graafi painotetuilla reunoilla. Polun pituus on tähän polkuun sisältyvien reunojen painojen summa. On löydettävä lyhyimmät polut valitusta kärjestä kaikkiin graafin pisteisiin. $G$ $s$

Huomaa, että lyhimpiä polkuja ei välttämättä ole olemassa. Joten kaaviossa, joka sisältää negatiivisen kokonaispainon omaavan syklin, on mielivaltaisen lyhyt polku tämän syklin yhdestä kärjestä toiseen (jokainen syklin kierros vähentää polun pituutta). Jaksoa, jonka reunapainotussumma on negatiivinen, kutsutaan negatiiviseksi sykliksi .

Tehtävän ratkaiseminen kaaviossa ilman negatiivisia syklejä

Ratkaistaan annettu tehtävä kaaviolla, jossa ei selvästikään ole negatiivisia syklejä.

Löytääksemme lyhimmät polut yhdestä kärjestä kaikkiin muihin, käytämme dynaamista ohjelmointimenetelmää . Muodostetaan matriisi, jonka alkiot osoittavat seuraavaa: on lyhimmän polun pituus kohteesta kohteeseen, joka sisältää enintään reunoja. $A_{{ij}}$ $a_{{ij}}$ $s$ $i$ $j$

Polku, jossa on 0 reunaa, on olemassa vain kärkeen asti . Siten se on yhtä suuri kuin 0, jos , ja muuten. $s$ ${\displaystyle A_{i0))$ $i=s$ $+\infty$

Harkitse nyt kaikkia polkuja kohteesta kohteeseen, jotka sisältävät tarkalleen reunat. Jokainen tällainen polku on polku reunasta, johon viimeinen reuna lisätään. Jos kaikki tiedot pituuspoluista on jo laskettu, ei ole vaikea määrittää matriisin saraketta. $s$ $i$ $j$ $j-1$ $j-1$ $j$

Tältä näyttää algoritmi kaavion lyhimpien polkujen pituuksien löytämiseksi ilman negatiivisia syklejä:

for do for do for jos sitten palaa

v\in V

d[v]\saa +\infty

d[s]\saa 0

saan 1

|V|-1

(u,v)\in E

d[v]>d[u]+w(u,v)

d[v]\saa d[u]+w(u,v)

d

Tässä on graafin kärkijoukko , on sen reunojen joukko ja on graafin reunoilla määritelty painofunktio (palauttaa kärjestä pisteeseen johtavan kaaren pituuden ), on matriisi, joka sisältää etäisyydet kohteesta kärjestä mihin tahansa toiseen kärkeen. $V$ $G$ $E$ $w$ $u$ $v$ $d$ $s$

Ulompi silmukka suoritetaan kerran, koska lyhin polku ei voi sisältää enempää reunoja, muuten se sisältää silmukan, joka voidaan ehdottomasti heittää ulos. $|V|-1$

Taulukon sijasta voit tallentaa koko matriisin , mutta tämä vaatii muistia. Mutta samalla voit laskea itse lyhyimmät polut, ei vain niiden pituutta. Tätä varten luomme matriisin . $d$ $A$ $O(V^{2})$ ${\displaystyle P_{ij))$

Jos elementti sisältää lyhimmän polun pituuden kohteesta kohteeseen sisältäviä reunoja, se sisältää edellisen kärjen kohteeseen jollakin näistä lyhyimmistä poluista (niitä voi olla useita). $A_{{ij}}$ $s$ $i$ $j$ ${\displaystyle P_{ij))$ $i$

Nyt Bellman-Ford-algoritmi näyttää tältä:

varten tehdä varten tehdä varten jos sitten _ _

v\in V

saan 0

|V|-1

A_{{vi}}\gets +\infty

A_{{s0}}\saa 0

saan 1

|V|-1

(u,v)\in E

A_{{vi}}>A_{{u,i-1}}+w(u,v)

A_{{vi}}\saa A_{{u,i-1}}+w(u,v)

P_{{vi}}\saa sinut

Tämän algoritmin suorittamisen jälkeen elementit sisältävät lyhimpien polkujen pituudet välillä - reunojen lukumäärällä , ja kaikista sellaisista poluista tulee valita lyhin. Ja lyhin polku kärkipisteeseen reunoilla palautetaan seuraavasti: $A_{{i,j}}$ $s$ $i$ $j$ $i$ $j$

palata s _

j>0

p[j]\saa i

saan P_{{ij}}

j\saa j-1

Kaavio negatiivisilla sykleillä

Bellman-Ford-algoritmin avulla on erittäin helppo määrittää, onko kaaviossa negatiivinen sykli, joka on saavutettavissa kärjestä . Riittää, kun suoritat silmukan ulomman iteroinnin ei , vaan täsmälleen kerran. Jos viimeisen iteraation suorituksen aikana lyhimmän polun pituus mihin tahansa kärkeen väheni tiukasti, niin kaaviolla on negatiivinen sykli, joka on saavutettavissa kohteesta . Tämän perusteella voimme ehdottaa seuraavaa optimointia: seurata kaavion muutoksia ja heti niiden päätyttyä poistua silmukasta (jatkuvat iteraatiot ovat merkityksettömiä). $G$ $s$ $|V|-1$ $|V|$ $s$

Kirjallisuus

R. Bellman: Reititysongelmasta // Quarterly of Applied Mathematics. 1958. Voi 16, no. 1. C. 87-90, 1958.
LR Ford, Jr., DR Fulkerson. Flows in Networks, Princeton University Press, 1962.

Katso myös

Linkit

Kaavion hakualgoritmit
Tietämättömät menetelmät	Kaksisuuntainen haku Säteen haku Leksikografinen leveys ensimmäinen haku Leveys ensimmäinen haku Hae kustannuskriteerin mukaan Ensimmäinen syvyyshaku Peruutushaku Hae kiipeämällä huipulle Syvyysrajoitettu haku Syvyys-ensin haku iteratiivisella syventämisellä
Tietoon perustuvat menetelmät	Alfa beta leikkaus Haara- ja sidontamenetelmä Hae ensimmäisen parhaan osuman perusteella A* B* D* Siirtymäkohdan löytäminen IDA* Rekursiivinen haku ensimmäisen parhaan osuman perusteella SMA*
Pikanäppäimet	Aalto-algoritmi Bellman-Ford-algoritmi Dijkstran algoritmi Johnsonin algoritmi Levitin algoritmi Floyd-Warshall-algoritmi Reunahaku
Vähintään ulottuva puu	Boruvkan algoritmi Primin algoritmi Kruskalin algoritmi
muu	British Museum Algorithm Edmondsin algoritmi Puun läpikulku Lähin naapuri -algoritmi matkustavan myyjän ongelmassa