| dbo:abstract
|
- Johnsonův algoritmus je algoritmus sloužící k hledání nejkratších cest mezi všemi uzly v ohodnoceném orientovaném grafu, který může mít záporně ohodnocené hrany. V řídkých grafech je rychlejší, než Floydův-Warshallův algoritmus. Johnsonův algoritmus dokáže rozpoznat záporný cyklus v grafu a výpočet ukončit. K tomu využívá Bellmanův-Fordův algoritmus, s jehož pomocí přehodnotí hrany tak, aby žádná neobsahovala zápornou hodnotu. Po přehodnocení hran používá Dijkstrův algoritmus k nalezení nejkratších cest mezi všemi uzly. Johnsonův algoritmus je pojmenován po Donaldu B. Johnsonovi. (cs)
- Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights. (en)
- En informatique, l'algorithme de Johnson calcule des plus courts chemins entre toutes les paires de sommets dans un graphe orienté, aux arcs pondérés. Les poids des arcs peuvent être des nombres négatifs pourvu qu'il n'existe pas de circuits de poids négatif. Il est particulièrement efficace lorsque le graphe est creux. L'algorithme opère en utilisant d'abord l'algorithme de Bellman-Ford pour calculer une transformation du graphe de départ qui supprime tous les poids négatifs, ce qui permet l'emploi, dans un deuxième temps, de l’algorithme de Dijkstra sur le graphe transformé. L'algorithme est nommé d'après (en) qui le premier a publié cette méthode en 1977. Une technique similaire de repondération est aussi utilisée dans l' (en) pour la recherche de deux chemins disjoints de longueur totale minimale entre deux même sommets dans un graphe pondéré positivement. (fr)
- El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso.Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la técnica en 1977. (es)
- Algorytm Johnsona – algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych na kopcach Fibonacciego), dla grafów rzadkich jest więc asymptotycznie szybszy od algorytmu Floyda-Warshalla. Algorytm Johnsona zwraca albo macierz wag najkrótszych ścieżek, albo informuje, że graf wejściowy ma cykl o ujemnej wadze. Algorytm Johnsona wykorzystuje algorytmy Dijkstry i Bellmana-Forda. (pl)
- Algoritmo de Johnson é uma forma de encontrar o menor caminho entre entre dois pontos. Ele permite que algumas arestas tenham número negativo, mas ciclos negativos não devem existir. Este algoritmo trabalha com base no Algoritmo de Bellman-Ford, para computar uma transformação de um grafo de entrada, que remove todas os pesos negativos, permitindo o uso do algoritmo de Dijkstra no grafo transformado. Recebe esse nome em homenagem a Donald B. Johnson, o primeiro a descrevê-lo, em 1977. (pt)
- Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює, якщо у графі містяться ребра з додатною чи від'ємною вагою, але відсутні цикли з від'ємною вагою. Названо на честь , який опублікував цей алгоритм 1977 року. (uk)
- Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.Назван в честь , опубликовавшего алгоритм в 1977 году. (ru)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7410 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:class
| |
| dbp:data
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Johnsonův algoritmus je algoritmus sloužící k hledání nejkratších cest mezi všemi uzly v ohodnoceném orientovaném grafu, který může mít záporně ohodnocené hrany. V řídkých grafech je rychlejší, než Floydův-Warshallův algoritmus. Johnsonův algoritmus dokáže rozpoznat záporný cyklus v grafu a výpočet ukončit. K tomu využívá Bellmanův-Fordův algoritmus, s jehož pomocí přehodnotí hrany tak, aby žádná neobsahovala zápornou hodnotu. Po přehodnocení hran používá Dijkstrův algoritmus k nalezení nejkratších cest mezi všemi uzly. Johnsonův algoritmus je pojmenován po Donaldu B. Johnsonovi. (cs)
- El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices de un grafo dirigido disperso.Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado. Su nombre viene de Donald B. Johnson, quien fuera el primero en publicar la técnica en 1977. (es)
- Algorytm Johnsona – algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych na kopcach Fibonacciego), dla grafów rzadkich jest więc asymptotycznie szybszy od algorytmu Floyda-Warshalla. Algorytm Johnsona zwraca albo macierz wag najkrótszych ścieżek, albo informuje, że graf wejściowy ma cykl o ujemnej wadze. Algorytm Johnsona wykorzystuje algorytmy Dijkstry i Bellmana-Forda. (pl)
- Algoritmo de Johnson é uma forma de encontrar o menor caminho entre entre dois pontos. Ele permite que algumas arestas tenham número negativo, mas ciclos negativos não devem existir. Este algoritmo trabalha com base no Algoritmo de Bellman-Ford, para computar uma transformação de um grafo de entrada, que remove todas os pesos negativos, permitindo o uso do algoritmo de Dijkstra no grafo transformado. Recebe esse nome em homenagem a Donald B. Johnson, o primeiro a descrevê-lo, em 1977. (pt)
- Алгоритм Джонсона дозволяє знайти найкоротші шляхи між усіма парами вершин зваженого орієнтованого графу. Цей алгоритм працює, якщо у графі містяться ребра з додатною чи від'ємною вагою, але відсутні цикли з від'ємною вагою. Названо на честь , який опублікував цей алгоритм 1977 року. (uk)
- Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся рёбра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.Назван в честь , опубликовавшего алгоритм в 1977 году. (ru)
- Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. (en)
- En informatique, l'algorithme de Johnson calcule des plus courts chemins entre toutes les paires de sommets dans un graphe orienté, aux arcs pondérés. Les poids des arcs peuvent être des nombres négatifs pourvu qu'il n'existe pas de circuits de poids négatif. Il est particulièrement efficace lorsque le graphe est creux. L'algorithme opère en utilisant d'abord l'algorithme de Bellman-Ford pour calculer une transformation du graphe de départ qui supprime tous les poids négatifs, ce qui permet l'emploi, dans un deuxième temps, de l’algorithme de Dijkstra sur le graphe transformé. L'algorithme est nommé d'après (en) qui le premier a publié cette méthode en 1977. (fr)
|
| rdfs:label
|
- Johnsonův algoritmus (cs)
- Algoritmo de Johnson (es)
- Algorithme de Johnson (fr)
- Johnson's algorithm (en)
- Algorytm Johnsona (pl)
- Algoritmo de Johnson (pt)
- Алгоритм Джонсона (ru)
- Алгоритм Джонсона (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:notableWorks
of | |
| is foaf:primaryTopic
of | |
