Use Dijkstra’s Algorithm to find the shortest paths from the source node to all other nodes.
Define a priority queue to store pairs of {dist, node}, where 'dist' represents the shortest distance from the source node to the current node.
Initialize a distance array with a very large number (∞) for all nodes, indicating they are unvisited, and set the source node’s distance to 0.
Define a ways array to store the number of shortest paths to each node, initialized to 0.
Push the source node into the queue with a distance of 0 and ways set to 1, as there is exactly one way to reach the source.
Pop the front element from the queue, examine its adjacent nodes, and check the current distance to each adjacent node.
If the current distance to a node is smaller than the previously stored distance, update the distance and push the node into the queue with the new distance. Also, set the ways for that node to the same value as the source node’s ways.
If the current distance equals the previously stored distance, increment the ways array at that node by 1 to account for an additional shortest path.
Repeat these steps until the queue is empty or the destination node is reached.
Finally, return the number of ways to reach the destination node (ways[n-1]) modulo 10^9+7 when the queue is empty.