Johnson's algorithm
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.
- Class
- All-pairs shortest path problem
- Comment
- enJohnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.
- Data
- Graph (data structure)
- Depiction
- Has abstract
- enJohnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977. A similar reweighting technique is also used in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.
- Is primary topic of
- Johnson's algorithm
- Label
- enJohnson's algorithm
- Link from a Wikipage to an external page
- www.boost.org/doc/libs/1_40_0/libs/graph/doc/johnson_all_pairs_shortest.html
- Link from a Wikipage to another Wikipage
- All-pairs shortest path problem
- Bellman–Ford algorithm
- Category:Graph algorithms
- Category:Graph distance
- Category:Search algorithms
- Cycle (graph theory)
- Dijkstra's algorithm
- Directed graph
- Donald B. Johnson
- Edge (graph theory)
- Fibonacci heap
- File:Johnson's algorithm.svg
- Floyd–Warshall algorithm
- Graph (data structure)
- Negative number
- Shortest path
- Sparse graph
- Suurballe's algorithm
- Time complexity
- Vertex (graph theory)
- Weighted graph
- SameAs
- 2DXvY
- Algorithme de Johnson
- Algoritmo de Johnson
- Algoritmo de Johnson
- Algorytm Johnsona
- Džonsonov algoritam
- Johnson's algorithm
- Johnson algoritması
- Johnson algoritmusa
- Johnsonův algoritmus
- m.04q0b2
- Q2345824
- Thuật toán Johnson
- Алгоритм Джонсона
- Алгоритм Джонсона
- האלגוריתם של ג'ונסון
- الگوریتم جانسون
- ขั้นตอนวิธีของจอห์นสัน
- Subject
- Category:Graph algorithms
- Category:Graph distance
- Category:Search algorithms
- Thumbnail
- WasDerivedFrom
- Johnson's algorithm?oldid=1089573529&ns=0
- WikiPageLength
- 7410
- Wikipage page ID
- 1284311
- Wikipage revision ID
- 1089573529
- WikiPageUsesTemplate
- Template:For
- Template:Infobox Algorithm
- Template:Math
- Template:Mvar
- Template:Reflist
- Template:Short description
- Template:Tmath
- Template:Tree search algorithm
