| Property |
Value |
| 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. (fr)
- 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)
|
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9105 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:fr
|
- Donald B. Johnson (fr)
- algorithme de Suurballe (fr)
- Donald B. Johnson (fr)
- algorithme de Suurballe (fr)
|
| prop-fr:lang
| |
| prop-fr:texte
|
- Donald B. Johnson (fr)
- Donald B. Johnson (fr)
|
| prop-fr:trad
|
- Donald B. Johnson (fr)
- Suurballe's algorithm (fr)
- Donald B. Johnson (fr)
- Suurballe's algorithm (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| 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)
- 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
|
- Algorithme de Johnson (fr)
- Johnson's algorithm (en)
- Thuật toán Johnson (vi)
- Алгоритм Джонсона (ru)
- Алгоритм Джонсона (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
