How to find the shortest path in a weighted graph(**if many then lexicographically smallest**) using Dijkstra? — I am getting WA on 2 test cases - Problem link :Your text to link here... - Although this can be solved using BFS, but I want to know do when the graph is weighted?
Let's assume X = 1. Using Dijkstra, calculate the distance Dv from node 1 to node v. For every node u, store Pu, the minimum v over all edges (v, u) such that Dv + w(v, u) = Du. It is easy to find this path now:
Got it!
Your solution is wrong. Consider this graph:
6 6
1 2 1
1 4 1
4 3 1
3 6 1
5 6 1
2 5 1
According to you shortest + lexographically shortest path will be 1 -> 4 -> 3 -> 6 while it should be 1 -> 2 -> 5 -> 6;