| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Algorithme de Johnson (fr)
- Johnson's algorithm (en)
- Thuật toán Johnson (vi)
- Алгоритм Джонсона (ru)
- Алгоритм Джонсона (uk)
|
| 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. (fr)
|
| sameAs
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| dbo:wikiPageWikiLink
| |
| Link from a Wikipage to an external page
| |
| page length (characters) of wiki page
| |
| dct:subject
| |
| prop-fr:wikiPageUsesTemplate
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| prop-fr:fr
| - Donald B. Johnson (fr)
- algorithme de Suurballe (fr)
|
| prop-fr:lang
| |
| prop-fr:texte
| |
| prop-fr:trad
| - Donald B. Johnson (fr)
- Suurballe's algorithm (fr)
|
| thumbnail
| |
| foaf:isPrimaryTopicOf
| |
| dbo:discoverer
| |
| named after
| |
| has 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. (fr)
|
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
![[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)
