Johnson Algorithm

[saiadityaviswanadham]

Is your feature request related to a problem? Please describe. The feature can be used to find out the shortest paths between two vertices.

Describe the solution you'd like ->Let the given graph be G. A new vertex v should be added to the graph, Later add edges from a new vertex to all vertices of graph G. The modified graph be G. ->Use the bellman-ford algorithm on G with v as a source point. The distances calculated by Bellman-Ford be h[0], h[1],..h[V-1]. Return it if you found a negative weighted cycle. Make a note that the negative weight cycle cannot be created by new vertex v as there is no edge to v. All edges are from v. ->Reweights the edges of the original graph. For each edge (x, y), assign the new weight as “original weight + h[x] – h[y].” ->Run the Dijkstra algorithm for every vertex after removing the added vertex s.

Describe alternatives you've considered Belman-Ford Algorithm and Dijkstra Algorithm's are used as part of Johnson Algorithm

[saiadityaviswanadham]

@Lakhankumawat As a part of GSSOC22, Can you assign me this issue..

[Abhilasha-Jairath]

I want to work on this under GSSOC2022. Can you assign it to me.

[navyasharma0203]

/assign

[github-actions[bot]]

The issue is already assigned! Please find/create a new issue to contribute to. You can safely disregard the failed workflow notification for this issue. ❌