. . . . . . . . . . . . "En informatique, l'algorithme de Johnson calcule des plus courts chemins entre toutes les paires de sommets dans un graphe orient\u00E9, aux arcs pond\u00E9r\u00E9s. Les poids des arcs peuvent \u00EAtre des nombres n\u00E9gatifs pourvu qu'il n'existe pas de circuits de poids n\u00E9gatif. Il est particuli\u00E8rement efficace lorsque le graphe est creux. L'algorithme op\u00E8re en utilisant d'abord l'algorithme de Bellman-Ford pour calculer une transformation du graphe de d\u00E9part qui supprime tous les poids n\u00E9gatifs, ce qui permet l'emploi, dans un deuxi\u00E8me temps, de l\u2019algorithme de Dijkstra sur le graphe transform\u00E9. L'algorithme est nomm\u00E9 d'apr\u00E8s (en) qui le premier a publi\u00E9 cette m\u00E9thode en 1977. Une technique similaire de repond\u00E9ration est aussi utilis\u00E9e dans l' (en) pour la recherche de deux chemins disjoints de longueur totale minimale entre deux m\u00EAme sommets dans un graphe pond\u00E9r\u00E9 positivement."@fr . . . . . . . . "9282157"^^ . . "Donald B. Johnson"@fr . . . . . . . . . . . "9105"^^ . . . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0414\u0436\u043E\u043D\u0441\u043E\u043D\u0430"@uk . "en"@fr . . "En informatique, l'algorithme de Johnson calcule des plus courts chemins entre toutes les paires de sommets dans un graphe orient\u00E9, aux arcs pond\u00E9r\u00E9s. Les poids des arcs peuvent \u00EAtre des nombres n\u00E9gatifs pourvu qu'il n'existe pas de circuits de poids n\u00E9gatif. Il est particuli\u00E8rement efficace lorsque le graphe est creux. L'algorithme op\u00E8re en utilisant d'abord l'algorithme de Bellman-Ford pour calculer une transformation du graphe de d\u00E9part qui supprime tous les poids n\u00E9gatifs, ce qui permet l'emploi, dans un deuxi\u00E8me temps, de l\u2019algorithme de Dijkstra sur le graphe transform\u00E9. L'algorithme est nomm\u00E9 d'apr\u00E8s (en) qui le premier a publi\u00E9 cette m\u00E9thode en 1977."@fr . . . . "Thu\u1EADt to\u00E1n Johnson"@vi . . . . . . . "183941515"^^ . . . . . . . . "Donald B. Johnson"@fr . "algorithme de Suurballe"@fr . "Johnson's algorithm"@en . . . . . . . "Donald B. Johnson"@fr . . . . . "Algorithme de Johnson"@fr . . . "\u0410\u043B\u0433\u043E\u0440\u0438\u0442\u043C \u0414\u0436\u043E\u043D\u0441\u043E\u043D\u0430"@ru . "Suurballe's algorithm"@fr . . . .