Algorithm Description
Johnson's algorithm consists of the following steps:
- First, a new node q is added to the graph, connected by zero-weight edges to each of the other nodes.
- Second, the Bellman–Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.
- Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from u to v, having length w(u,v), is given the new length w(u,v) + h(u) − h(v).
- Finally, q is removed, and Dijkstra's algorithm is used to find the shortest paths from each node s to every other vertex in the reweighted graph.
Read more about this topic: Johnson's Algorithm
Famous quotes containing the word description:
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)