Create hupJuv.js

[06Vikrant]

📑 DESCRIPTION

Issue Number : #1201 by @06Vikrant

❓ What has been changed : Created a JavaScript program to find the shortest path in a directed weighted graph with more than 10 million nodes and edges

• Given a directed graph where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(V+E).

• A Simple Solution is to use Dijkstra’s shortest path algorithm, we can get a shortest path in O(E + VLogV) time.

How to do it in O(V+E) time?

• The idea is to use BFS. One important observation about BFS is that the path used in BFS always has the least number of edges between any two vertices. So if all edges are of same weight, we can use BFS to find the shortest path. For this problem, we can modify the graph and split all edges of weight 2 into two edges of weight 1 each. We can use BFS to find the shortest path in the modified graph.

How many new intermediate vertices are needed?

• We need to add a new intermediate vertex for every source vertex. The reason is simple, if we add an intermediate vertex x between u and v and if we add same vertex between y and z, then new paths u to z and y to v are added to the graph which might have not been there in the original graph. Therefore in a graph with V vertices, we need V extra vertices. Below is the C++ implementation of the above idea. In the below implementation 2*V vertices are created in a graph and for every edge (u, v), we split it into two edges (u, u+V) and (u+V, w). This way, we ensure that a different intermediate vertex is added for every source vertex.

Output

Shortest Path between 0 and 3 is 0 1 3 Shortest Distance between 0 and 3 is 3

Time Complexity: O(V + E)

• In this algorithm, we do a Breadth First Traversal of the given graph. The time complexity of BFS is O(V + E) where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V)

• The space complexity for this algorithm is O(V), where V is the number of vertices in the graph. We need to store the visited array of size V and a parent array of size V.

• How is this approach O(V+E)? In worst case, all edges are of weight 2 and we need to do O(E) operations to split all edges and 2V vertices, so the time complexity becomes O(E) + O(V+E) which is O(V+E).

Fixes #1201

[sourcefusionhub-automation[bot]]

Please follow @CodingWithHardik for further instructions on how to proceed with this pull request. To check the follow status use !check