This HTML5 document contains 81 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
n17http://hu.dbpedia.org/resource/Sablon:Hivatkozás/
n4http://safari.oreilly.com/0201361213/
n8http://www.rand.org/pubs/papers/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n12https://web.archive.org/web/20080531142256/http:/safari.oreilly.com/0201361213/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n7http://hu.dbpedia.org/resource/Sablon:
n16http://homepages.cwi.nl/~lex/files/
n11http://www.cs.rhul.ac.uk/books/dbook/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n14http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Bellman–Ford-algoritmus
rdfs:label
Bellman–Ford-algoritmus
dct:subject
n14:Gráfalgoritmusok
dbo:wikiPageID
1710195
dbo:wikiPageRevisionID
23221596
dbo:wikiPageExternalLink
n4:ch21lev1sec7 n12:ch21lev1sec7 n11: n16:histco.pdf%7Cref=harv n8:P923.html
prop-hu:wikiPageUsesTemplate
n7:Wayback n7:Harvard_citations n7:Sfnp n7:Cite_journal n7:Cite_book n7:Cite_conference n7:ISBN n17:Könyv n7:Fordítás n7:Jegyzetek
prop-hu:accessdate
2007-05-28
prop-hu:authorlink
Robert Sedgewick L. R. Ford Jr.
prop-hu:chapter
Section 2.3.4: The Bellman-Ford-Moore algorithm Chapter 6: Graph Algorithms Section 21.7: Negative Edge Weights
prop-hu:date
20080531142256 1956-08-14
prop-hu:edition
3.0 First
prop-hu:first
Gregory Lester R. Jr. Gary Robert Stanley Jon George T. Jørgen Éva
prop-hu:isbn
978 0
prop-hu:last
Tardos Selkow Ford Bang-Jensen Gutin Kleinberg Heineman Sedgewick Pollice
prop-hu:location
New York Santa Monica, California
prop-hu:pages
160
prop-hu:publisher
RAND Corporation Pearson Education, Inc. dbpedia-hu:O'Reilly_Media
prop-hu:ref
harv
prop-hu:series
Paper P-923
prop-hu:title
Network Flow Theory Algorithms in Java Algorithms in a Nutshell Algorithm Design Digraphs: Theory, Algorithms and Applications
prop-hu:url
n4:ch21lev1sec7 n8:P923.html n11:
prop-hu:year
2008 2006 2002 2000
prop-hu:accessDate
2007-05-28
prop-hu:archiveUrl
n12:ch21lev1sec7
prop-hu:urlStatus
dead
prop-hu:author1Link
Jon Kleinberg
prop-hu:author2Link
Éva Tardos
prop-hu:archiveDate
2008-05-31
dbo:abstract
A Bellman–Ford-algoritmus egy algoritmus, amely kiszámítja egyetlen forrástól (vertex) az összes többi csúcshoz egy súlyozott digráfban. Ez lassabb, mint Dijkstra algoritmusa ugyanarra a problémára, viszont sokoldalúbb, mert képes olyan grafikonok kezelésére, amelyekben az egyes élsúlyok negatív számok. Az algoritmust először Alfonso Shimbel javasolta, azonban helyette Richard Bellman és Lester Ford Jr. után nevezték el, akik 1958-ban, illetve 1956-ban publikálták. Edward F. Moore is közzétette ugyanezt az algoritmust 1957-ben, ezért néha Bellman–Ford–Moore-algoritmusnak is nevezik. A negatív élsúlyok a gráfok különböző alkalmazásaiban találhatóak, innen ered az algoritmus hasznossága. Ha egy gráf tartalmaz egy "negatív ciklust" (azaz egy olyan ciklust, amelynek élei összege negatív értékűek), amely elérhető a forrástól, akkor nincs legolcsóbb út: bármely olyan út, amelynek van egy pontja a negatív körön, olcsóbbá válhat egy további sétával a negatív ciklus mentén. Ilyen esetben a Bellman–Ford-algoritmus képes felismerni és jelenteni a negatív ciklust. Mint Dijkstra algoritmusa Bellman–Ford relaxáció útján megy végbe, amelyben a helyes távolságokhoz való közelítéseket jobbak váltják fel, amíg végül el nem érik a megoldást. Mindkét algoritmusban az egyes csúcsokhoz való hozzávetőleges távolság mindig a valós távolság túlbecslése, és helyébe a régi érték minimuma és az újonnan talált út hossza lép Dijkstra algoritmusa azonban prioritási sort használ, hogy mohón kiválassza a még nem feldolgozott legközelebbi csúcsot, és végrehajtja ezt a relaxációs folyamatot az összes kimenő élen; ezzel szemben a Bellman–Ford-algoritmus egyszerűen ellazítja az összes élt, és ezt meg is teszi alkalommal, ahol a csúcsok száma a gráfon. Ezen ismétlések mindegyikében növekszik a helyesen kiszámított távolsággal rendelkező csúcsok száma, amelyből az következik, hogy végül az összes csúcs megfelelő távolsággal fog rendelkezni. Ez a módszer lehetővé teszi a Bellman–Ford-algoritmus a Dijkstránál szélesebb bemeneti osztályra történő alkalmazását. Bellman–Ford időben zajlik, ahol és a csúcsok és az élek száma. függvény BellmanFord(list vertices, list edges, vertex source) is ::distance[], predecessor[] // Ez a megvalósítás egy gráfba kerül, mint // csúcsa gráf ok és élek listái és két sort tölt meg // (távolság és előd) a legrövidebb útról // a forrástól minden egyes csúcshoz. // 1. lépés: gráf inicializálás for each vertex v in vertices do distance[v] := '''inf''' // A távolság minden csúcshoz történő inicializálása a végtelenig predecessor[v] := '''null''' // És van egy null elődjeőddel distance[source] := 0 // A távolság a forrástól önmagához természetesen nulla // 2. Lépés: az élek ismétlődő lazítása '''for each''' edge (u, v) '''with''' weight w '''in''' edges '''do''' '''if''' distance[u] + w < distance[v] '''then''' distance[v] := distance[u] + w predecessor[v] := u // 3. lépés: a negatív súlyú ciklus ellenőrzése '''for each''' edge (u, v) '''with''' weight w '''in''' edges '''do''' '''if''' distance[u] + w < distance[v] '''then''' '''error''' "A gráf negatív súlyú ciklust tartalmaz” '''return''' distance[], predecessor[] Leegyszerűsítve, az algoritmus inicializálja a forráshoz való távolságot 0-ig, és minden többi csomópontot a végtelenig. Ezt követően az összes él esetében, ha a távolság a rendeltetési helyig lerövidíthető az él megvételével, a távolság az új,alacsonyabb értékre frissül. Minden egyes i iterációnál, az élek vizsgálatakor, az algoritmus megtalálja a leghosszabb i élek összes legrövidebb útját (és esetleg néhány i élnél hosszabb utat is). Mivel a ciklus nélküli lehető leghosszabb út lehet él, az éleket meg kell vizsgálni alkalommal annak biztosítékaként, hogy minden csomópontra megtalálták a legrövidebb utat. Az összes él végső vizsgálatát elvégzik, és amennyiben bármelyik távolságot frissítik, akkor megtalálják a hosszúságú élek útját, amely csak akkor fordulhat elő, ha legalább egy negatív ciklus létezik a gráfban.
prov:wasDerivedFrom
wikipedia-hu:Bellman–Ford-algoritmus?oldid=23221596&ns=0
dbo:wikiPageLength
17296
foaf:isPrimaryTopicOf
wikipedia-hu:Bellman–Ford-algoritmus
Subject Item
dbpedia-hu:Bellman–Ford_algoritmus
dbo:wikiPageRedirects
dbpedia-hu:Bellman–Ford-algoritmus
Subject Item
wikipedia-hu:Bellman–Ford-algoritmus
foaf:primaryTopic
dbpedia-hu:Bellman–Ford-algoritmus