algorithme de Johnson
Sign in to savealgorithm to find shortest paths between all pairs of vertices in a sparse, edge-weighted (possibly negatively), directed graph; uses the Bellman–Ford algorithm to remove negative weights and Dijkstra’s algorithm on the rest
Wikidata facts
- Instance of
- shortest path problem
Show 3 more facts
- publication date
- 1977-00-00
- Commons category
- Johnson's algorithm
Sources (1)
via Wikidata · CC0
Article · Français
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.
Abstract from DBpedia / Wikipedia · CC BY-SA