[C++/Python] Dijkstra - Clean & Concise
Idea\n- We use Dijkstra algorithm to find the Shortest Path from src = 0 to dst = n - 1.\n- While dijkstra, we create additional ways array, where ways[i] keeps
**Idea**\n- We use Dijkstra algorithm to find the Shortest Path from `src = 0` to `dst = n - 1`.\n- While dijkstra, we create additional `ways` array, where `ways[i]` keeps the number of shortest path from `src = 0` to `dst = i`. Then the answer is `ways[n-1]`.\n\n<iframe src="https://leetcode.com/playground/PhVJCRs6/shared" frameBorder="0" width="100%" height="700"></iframe>\n\n**Complexity**\n- Time: `O(M * logN + N)`, where `M <= N*(N-1)/2` is number of roads, `N <= 200` is number of intersections.\n- Space: `O(N + M)`\n\n**Question & Answer**\n1. Should I remove this line `if dist[u] < d: continue  # Skip if d is not updated to latest version!`?\n\tIf you remove that line, the time complexity becomes `O(V^3 * logV)`, which can run pass all the testcases since `V <= 200`.\n\tBut if you keep that line, the time complexity reduces to `O(V^2 * logV)`.\n\tExplain: Other neightbors may visit node `u` multiple times (up to `O(V)` times) and push node `u` to the `minHeap`. In the worst case, node `u` will pop and process `O(V)` times, each time it takes `O(V)` to visit neighbors, there is up to `V` nodes like node `u`. So total time complexity is `O(V^3 * logV)`.\n\t\n\tCan check the following special graph (Not related to this problem)\n\t<img src="https://assets.leetcode.com/users/images/6e4e608c-950c-4606-ad37-3d38467cf67e_1629566004.4643087.png" alt="TLE Testcase Dijkstra" width="600"/>\n\tAnd this implementation https://ideone.com/lOoDHO will cause TLE.\n\t\n\t\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]