Number of Ways to Arrive at Destination - Solution & Explanation

Description: This approach extends the classic Dijkstra's algorithm by integrating path counting. During the process of finding the shortest path using Dijkstra's algorithm, we will maintain an additional array to count the number of ways to reach each node in the graph in the shortest time.

Steps:

1. Initialize a distance array to store shortest distances, setting all to infinity except the source, which is 0.
2. Initialize a ways array to count ways to reach each node, setting all to 0 except the source, which is 1.
3. Process each node using a priority queue, similar to Dijkstra's algorithm.
4. Whenever a new shortest path to a node is found, update the distance and ways count for that node.
5. Whenever another path is found with the same shortest distance, increment the ways count by the value from the parent node.
6. Continue until all nodes are processed.

Considerations: Ensure counting is done modulo 10⁹ + 7 to handle large numbers.

This Python function utilizes Dijkstra's algorithm via a min-heap (priority queue) to compute the shortest travel time. It adds functionality to track the number of shortest paths leading to each node. Each time a node is visited, if a shorter path is found, it updates; if equally short, it increments the path count using modular arithmetic.

Description: An adaptation of the Bellman-Ford algorithm is possible here due to its suitability for graphs with non-negative weights, though less efficient, still valid for counting shortest paths under simple constraints.

Steps:

1. Initialize distances with infinity and set the source distance to 0.
2. Initialize a ways array, set ways from the source to 1.
3. Relax all edges N-1 times: for every edge, update distance and path counts.
4. For the nth RELAXATION, update only if equal distance to handle multiple shortest paths.
5. Repeat updates for n-1 iterations to saturate shortest distances.

Note: Though not the most optimized under standard constraints as seen with Dijkstra's, exploring this aids learning.

The Java solution employs Bellman-Ford to establish shortest paths by iteratively relaxing all edges. Additional logic manages path counting upon equal length paths. Repeated edge checks across (n-1) rounds ensure comprehension of total optimal paths.