sir, we have represented graphs using hashmaps and we use GenericHeaps to implement Djikstra algorithm but this method seems to be pretty lengthy to code is there any other way to represent graphs and solve such problems
Djikstra Algorithm
@Siddharth_sharma1808,
you can also use adjacency matrix approach.
In this problem, for a given graph G with N vertices, M undirected edges with integer weights between them, and special vertex S, the goal is to find the length of the shortest paths from S to each of all N vertices.
This problem is formally called Single Source Shortest Path problem.
If all edges of G have non-negative weights, the most well-known and also widely used method of solving this problem is to use Dijkstra’s algorithm implemented with a priority queue. In that case, the total time complexity of the algorithm is O(MlogN). This is true because each edge of the graph is examined exactly once, and such an examination can cause a constant number of updates in a priority queue containing either O(N) or O(M) vertices depending on the implementation. However, since each such operation on a priority queue has complexity proportional to the logarithm of its size, it does not matter if the queue contains O(N) or O(M) entries, since logM <= 2logN because M is at most N2 in this problem.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.