Johnson’s algorithm – Knowledge and References

Explore chapters and articles related to this topic

Optimal Graph Traversals

Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018

Jonathan L. Gross, Jay Yellen, Mark Anderson

The idea behind the Edmonds and Johnson algorithm is to retrace the edges on certain shortest paths between odd-degree vertices, where the edge-weights are regarded as distances. If the edges of a path between two odd-degree vertices are duplicated, then the degrees of those two vertices become even and the parity of the degree of each internal vertex on the path remains the same.

A Centrality Index Based Approach for Selection of Optimal Location of Static Reactive Power Compensator

View Article

Journal Information

Published in Electric Power Components and Systems, 2018

Dibya Bharti, Mala De

Let’s now focus on the modified 5-bus test system as shown in Figure 2 having the system data given in Table 2. In this case, some shortest paths are directly connected path and some paths contain one or multiple intermediate buses as shown in Table 3. The shortest path search is based on Johnson’s algorithm. Johnson’s algorithm is popularly used for finding the shortest paths between all pairs of vertices in a sparse and edge weighted graph which are typical characteristics of a practical power system and hence, Johnson’s algorithm is chosen here. In proposed methodology, impedance is used as weights of edges of the graph.

Johnson's algorithm

Explore chapters and articles related to this topic

Optimal Graph Traversals

A Centrality Index Based Approach for Selection of Optimal Location of Static Reactive Power Compensator