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:
“He hath achieved a maid
That paragons description and wild fame;
One that excels the quirks of blazoning pens.”
—William Shakespeare (1564–1616)