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
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
n21http://commons.dbpedia.org/resource/Category:
dbpedia-eshttp://es.dbpedia.org/resource/
n31http://g.co/kg/m/
dbpedia-trhttp://tr.dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n24http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-cshttp://cs.dbpedia.org/resource/
n28http://fr.dbpedia.org/resource/Modèle:Boîte_déroulante/
n11http://fr.dbpedia.org/resource/Modèle:
n33http://fr.dbpedia.org/resource/Fichier:
wikipedia-frhttp://fr.wikipedia.org/wiki/
n9http://fr.dbpedia.org/resource/Modèle:Traduction/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-vihttp://vi.dbpedia.org/resource/
n15http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
prop-frhttp://fr.dbpedia.org/property/
dbpedia-thhttp://th.dbpedia.org/resource/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Algorithme_de_Johnson
rdf:type
wikidata:Q8366 dbo:Algorithm owl:Thing
rdfs:label
Алгоритм Джонсона Thuật toán Johnson Johnson's algorithm Algorithme de Johnson Алгоритм Джонсона
rdfs:comment
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.
owl:sameAs
dbpedia-he:האלגוריתם_של_ג'ונסון dbpedia-ru:Алгоритм_Джонсона n15:10187374 dbpedia-th:ขั้นตอนวิธีของจอห์นสัน dbpedia-fa:الگوریتم_جانسون dbr:Johnson's_algorithm n21:Johnson's_algorithm dbpedia-pt:Algoritmo_de_Johnson dbpedia-es:Algoritmo_de_Johnson wikidata:Q2345824 dbpedia-cs:Johnsonův_algoritmus dbpedia-uk:Алгоритм_Джонсона dbpedia-pl:Algorytm_Johnsona dbpedia-tr:Johnson_algoritması n31:04q0b2 dbpedia-hu:Johnson_algoritmusa dbpedia-vi:Thuật_toán_Johnson dbpedia-sr:Džonsonov_algoritam
dbo:wikiPageID
9282157
dbo:wikiPageRevisionID
183941515
dbo:wikiPageWikiLink
dbpedia-fr:Graphe_orienté dbpedia-fr:Informatique dbpedia-fr:Complexité_en_temps category-fr:Algorithme_de_la_théorie_des_graphes dbpedia-fr:Algorithme_de_Floyd-Warshall dbpedia-fr:Nombre_négatif dbpedia-fr:Densité_d'un_graphe dbpedia-fr:Algorithme_de_Dijkstra dbpedia-fr:Tas_de_Fibonacci dbpedia-fr:Graphe_(mathématiques_discrètes) dbpedia-fr:Circuit_(théorie_des_graphes) dbpedia-fr:Lexique_de_la_théorie_des_graphes dbpedia-fr:Algorithme_de_Bellman-Ford n33:Algorithme_de_johnson_3.svg n33:Algorithme_de_johnson_étape_4.jpg n33:Algorithme_de_johnson2.svg dbpedia-fr:Problème_de_plus_court_chemin n33:Algorithme_de_johnson_1.svg dbpedia-fr:Somme_télescopique
dbo:wikiPageExternalLink
n24:johnson_all_pairs_shortest.html
dbo:wikiPageLength
9105
dct:subject
category-fr:Algorithme_de_la_théorie_des_graphes
prop-fr:wikiPageUsesTemplate
n9:Référence n11:Refm n11:Math n11:Infobox_Algorithme2 n11:Lien n11:Souligner n11:Voir_homonyme n11:' n11:, n11:! n28:fin n11:Références n11:Portail n28:début
prov:wasDerivedFrom
wikipedia-fr:Algorithme_de_Johnson?oldid=183941515&ns=0
foaf:depiction
n10:Algorithme_de_johnson2.svg n10:Algorithme_de_johnson_étape_4.jpg n10:Algorithme_de_johnson_1.svg n10:Algorithme_de_johnson_3.svg
prop-fr:fr
Donald B. Johnson algorithme de Suurballe
prop-fr:lang
en
prop-fr:texte
Donald B. Johnson
prop-fr:trad
Donald B. Johnson Suurballe's algorithm
dbo:thumbnail
n10:Algorithme_de_johnson_1.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Algorithme_de_Johnson
dbo:discoverer
wikidata:Q5293994
dbo:namedAfter
wikidata:Q5293994
dbo:abstract
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.