Visual Explanation of Johnson’s Algorithm Johnson’s algorithm finds the shortest paths between all pairs of vertices in a directed graph. It converts negative edge weights into non-negative edge links. It does this by using the Bellman-Ford algorithm to remove all negative weights. It then allows Dijkstra’s algorithm to be used on the new graph. Let’s start with an example. Since this graph contains negative edges, Dijkstra’s algorithm cannot be applied to it yet. To begin, the edge links must be transformed to contain non-negative numbers. Johnson’s algorithm starts off by selecting a source vertex. The problem with choosing an existing