Tackling a Shortest Path Having a Negative Cycle by using Johnson's Calculation

Authors

  • K. Umamaheswari
  • A. Pavithra
  • S. Srinivashini
  • S. Subipriya

Abstract

In graph theory numerous calculations are utilized to discover shortest path, for example, Dijkstra's calculation and Bellman fort calculation.  In this paper, we solve a negative cycle in the directed graph and find shortest path for it. Here, we use Johnson's calculation for finding shortest path between the pair of vertex. Johnson's calculation use Bellman-ford calculation to distinguish negative cycle and afterward it is utilized by Johnson's calculation to wipe out the negative edge and reweight the edges in directed graph. Presently the Johnson's calculation solves the upgraded directed graph utilizing Dijkstra's shortest path calculation to discover most brief way between all pair of vertices. The yield of the calculation is the result of the original directed graph. Consider 5 towns A, B, C, D, and E. The sales guy begins from the metropolis A and he visits all other cities B, C, D, E. Find a minimal route of for all pair of vertices. The result is received through the use of Johnson’s calculation.

Downloads

Published

2019-12-23

Issue

Section

Articles