Metraipolis › archive › dc_02cb40062d41

Algorithme de Johnson — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_de_Johnson
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T11:43:23.965Z
SHA-256 of the archived text
ae5ca42200fc86bbf1e7090308c084a94623d884180a00b19138e3e9417e0287
Stable URL of this page
https://metraipolis.com/documento/dc_02cb40062d41

How to cite

Algorithme de Johnson — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Johnson (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_02cb40062d41 (Metraipolis archive dc_02cb40062d41, sha256 ae5ca42200fc86bbf1e7090308c084a94623d884180a00b19138e3e9417e0287)
BibTeX
@misc{dc02cb40062d41,
  title = {Algorithme de Johnson — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Johnson},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_02cb40062d41; sha256 ae5ca42200fc86bbf1e7090308c084a94623d884180a00b19138e3e9417e0287},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Johnson. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 Donald B. Johnson (en) qui le premier a publié cette méthode en 1977. Une technique similaire de repondération est aussi utilisée dans l'algorithme de Suurballe (en) pour la recherche de deux chemins disjoints de longueur totale minimale entre deux même sommets dans un graphe pondéré positivement.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Algorithme de Johnson» — https://fr.wikipedia.org/wiki/Algorithme_de_Johnson
Wikidata Q2345824: «algorithm 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» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2345824
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Johnson?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 224234663, consultata il 2026-10-17T11:14:12.553Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 8e9184e3483de631e4ad0e9481b63457d0c58ada8c9a5ba85981d9563972d5fa