Johnson's Algorithm in C, C++, Java and Python

[Kumar-laxmi]

Feature = Johnson's Algorithm

• Johnson's algorithm is capable of finding the shortest paths between all pairs of vertices, even in the presence of negative edge weights.
• It uses the Bellman-Ford algorithm to handle negative edge weights and identify negative cycles
• By transforming the graph and modifying the edge weights, it ensures that Dijkstra's algorithm can be applied effectively.

Appraoch :

1.Graph Transformation:

• Add a new vertex to the graph and connect it to all existing vertices with zero-weight edges.
• Assign zero weights to these new edges.

2. Bellman-Ford Algorithm:

   • Use the Bellman-Ford algorithm to calculate the shortest distances from the newly added vertex to all other vertices in the graph.
   • If a negative cycle is detected during this step, terminate the algorithm as it indicates that the graph contains no shortest paths.

3. Graph Modification:

   • Modify the weights of the original graph based on the results of the Bellman-Ford algorithm.
   • For each edge (u, v) in the graph, update its weight as the sum of its original weight and the distance from the newly added vertex to u minus the distance from the newly added vertex to v.

4. Dijkstra's Algorithm (Multiple Times):

   • Apply Dijkstra's algorithm to each vertex in the modified graph to find the shortest paths from that vertex to all other vertices.
   • This step is performed multiple times, once for each vertex in the graph.

Additional context

[tarunvyshnav777]

@Kumar-laxmi kindly assign this to me under SSOC'23

[Mrudula1205]

@Kumar-laxmi I would like to work on this issue. Please assign it to me

[Devchawla2608]

@Kumar-laxmi kindly assign this to me under SSOC'23. I'm ready to contribute in all 4 languages

[Shankhadweep]

@Kumar-laxmi Kindly assign this issue to me. I would like to work on this issue under SSOC'23.

[Kumar-laxmi]

Assigned! @Shankhadweep : C, C++, Python and Java

Unassigned @Shankhadweep

[shanvijha30]

@Kumar-laxmi Please assign this issue to me I would like to work on it. Thank you!

[Kumar-laxmi]

Assigned! @tarunvyshnav777 : C, C++, Java & Python

[Aarsh30]

if any one is not doing these algo let me know i would like to work on this @Kumar-laxmi assign it to me thank you

[tarunvyshnav777]

I'm working on it. By the end of today, I will submit my pr

[github-actions[bot]]

Stale issue message