| rdfs:comment
| - Bellmanův–Fordův algoritmus počítá nejkratší cestu v ohodnoceném grafu z jednoho uzlu do uzlu dalšího (do ostatních uzlů), kde mohou být některé hrany ohodnoceny i záporně. Dijkstrův algoritmus tento problém řeší sice v kratším čase, ale vyžaduje nezáporné ohodnocené hrany. Proto se Bellmanův–Fordův algoritmus používá i pro grafy se záporně ohodnocenými hranami. Algoritmus je používán například ve směrovacím protokolu RIP. (cs)
- خوارزمية بلمان - فورد (بالإنجليزية: Bellman–Ford algorithm) تقوم بحساب الطريق الأقصر والأسرع في مخطط موجه من خلال مصدر القمة، على عكس فانها تقوم بحساب الحواف الموجهة السالبة (إضافة إلى الموجبة)، و تمت تسميتها نسبة للعالمين ريتشارد بلمان وفورد لستر.تسمح هذه الخوارزمية بوجود عدة أقواس أو دوائر ذات اتجاه سالب كما تسمح بالكشف عن وجود دوائر ماصة أي دوائر ذات وزن إجمالي سالب (اتجاه سالب)، قابلة للحصول من مصدر القمة. (ar)
- ベルマン–フォード法 (英: Bellman–Ford algorithm) は、重み付き有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 によれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」。G を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、G における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。 (ja)
- 벨먼-포드 알고리즘(영어: Bellman-Ford algorithm)은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 데이크스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로, 이런 경우에는 벨먼-포드 알고리즘을 사용한다. V와 E가 각각 그래프에서 꼭짓점과 변의 개수라고 한다면, 벨먼-포드 알고리즘의 실행시간은 이다. (ko)
- Het algoritme van Bellman-Ford is een graaf-algoritme dat, voor een gegeven knoop van een gerichte graaf, de kortste route naar alle knopen van die graaf bepaalt. Het algoritme van Dijkstra lost dit probleem sneller op, maar dat algoritme kan alleen gebruikt worden bij een graaf met niet-negatieve gewichten. Het algoritme van Bellman-Ford wordt dus in de praktijk alleen gebruikt bij een graaf met negatieve gewichten. Het algoritme van Bellman-Ford kan namelijk een negatieve cirkel opsporen. Het algoritme is genoemd naar zijn ontwikkelaars, en . (nl)
- Алгоритм Беллмана — Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана — Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. Алгоритм маршрутизации RIP (алгоритм Беллмана — Форда) был впервые разработан в 1969 году, как основной для сети ARPANET. (ru)
- O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um digrafo (grafo orientado ou dirigido) ponderado, ou seja, cujas arestas têm peso, inclusive negativo. O Algoritmo de Dijkstra resolve o mesmo problema, num tempo menor, porém exige que todas as arestas tenham pesos positivos. Portanto, o algoritmo de Bellman-Ford é normalmente usado apenas quando existem arestas de peso negativo. O algoritmo de Bellman-Ford executa em tempo onde V é o número de vértices e E o número de arestas. (pt)
- 贝尔曼-福特算法（英語：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·貝尔曼（Richard Bellman） 和 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 也为这个算法的发展做出了贡献。它的原理是对图进行次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达。但算法可以进行若干种优化，提高了效率。 (zh)
- Алгоритм Беллмана—Форда — алгоритм пошуку найкоротшого шляху в зваженому графі. Знаходить найкоротші шляхи від однієї вершини графу до всіх інших. На відміну від алгоритму Дейкстри, алгоритм Беллмана—Форда допускає ребра з негативною вагою. Запропоновано незалежно Річардом Беллманом і . (uk)
- L'algorisme de Bellman-Ford (o algorisme de Bell-End-Ford) genera el camí més curt en un graf dirigit ponderat en què el pes de les pot ser negatiu. L'algorisme de Dijkstra resol aquest mateix problema en un temps menor, però requereix que els pesos de les arestes no siguin negatius. Aquest algorisme va ser desenvolupat per Richard Bellman, Samuel End i Lester Ford. (ca)
- The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.The algorithm was first proposed by Alfonso Shimbel, but is instead named after Richard Bellman and Lester Ford Jr., who published it in and , respectively. Edward F. Moore also published a variation of the algorithm in , and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm. (en)
- Der Algorithmus von Bellman und Ford (nach seinen Erfindern Richard Bellman und Lester Ford) ist ein Algorithmus der Graphentheorie und dient der Berechnung der kürzesten Wege ausgehend von einem Startknoten in einem kantengewichteten Graphen. Gelegentlich wird auch vom Moore-Bellman-Ford-Algorithmus gesprochen, da auch Edward F. Moore zu seiner Entwicklung beigetragen hat. (de)
- El algoritmo de Bellman-Ford genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford. (es)
- L'algorithme de Bellman-Ford, aussi appelé algorithme de Bellman–Ford–Moore, est un algorithme qui calcule des plus courts chemins depuis un sommet source donné dans un graphe orienté pondéré. Il porte le nom de ses inventeurs Richard Bellman et Lester Randolph Ford junior (publications en 1956 et 1958), et de Edward Forrest Moore qui le redécouvrit en 1959. La complexité de l'algorithme est en où est le nombre de sommets est le nombre d'arcs. (fr)
- Algoritme Bellman–Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraf berbobot.Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritme Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritme Bellman-Ford hanya digunakan jika ada sisi berbobot negatif. Algoritme Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah banyaknya sisi dan titik. Dalam konteks ini, dengan jarak dalam sebuah sisi.
* l
*
* s (in)
- L'algoritmo di Bellman-Ford calcola i cammini minimi di un'unica sorgente su un grafo diretto pesato (dove alcuni pesi degli archi possono essere negativi). L'algoritmo di Dijkstra risolve lo stesso problema in un tempo computazionalmente inferiore, ma richiede che i pesi degli archi siano non-negativi. Per questo, Bellman-Ford è usato di solito quando sul grafo sono presenti pesi degli archi negativi. (it)
- Algorytm Bellmana-Forda – algorytm służący do wyszukiwania najkrótszych ścieżek w grafie ważonym z wierzchołka źródłowego do wszystkich pozostałych wierzchołków. Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja razy każdej z krawędzi). W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda działa poprawnie także dla grafów z wagami ujemnymi (nie może jednak wystąpić cykl o łącznej ujemnej wadze osiągalny ze źródła). Za tę ogólność płaci się jednak wyższą złożonością czasową. Działa on w czasie . (pl)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)