Given an adjacency list of a weighted, undirected graph with "v" vertices (0 to v-1) and a source node "source".
The task is to find the shortest path possible from the source node to every other node in the graph.
Note: The graph doesn't contain any negative weight cycles.
Solutions
Method 1: Dijkstra's Algorithm
In order to implement Dijkstra's Algorithm, we need a priority-queue and a distance array, shortestPaths[].
Initialise the shortestPaths[] array with infinity (Integer.MAX_VALUE) indicating that at present none of the nodes are reachable from the source node.
Also initialise the distance to the source node as 0 and push the source node to the queue.
For each iteration, look out for adjacent nodes for every node polled out of the priority queue.
If the current reachable distance is less than the previous distance indicated by the distance array, we update the distance and push it in the queue.
Note: Djikstra's algorithm might work in some cases and fail in others if there is an edge with negative weight.
Complexity
The time complexity of this solution is O(V^2) and space complexity is O(V^2).