Although my solution is AC (1.5 sec in undirected graph , 1.01 sec in directed graph) , can we do better than " K*(E+ VlogV) " as simple approach is just call Dijkstra each time with given source and destination.
You can indeed speed up dijkstra using a fibonacci heap instead of a Binary Heap. Other faster implementations of Dijkstra do exist. Refer to CLRS for the references to the papers.
Always use Dijkistra (in case of +ve weighted edge and number of edges are less) as it’s complexity is less than either Bellman-ford or Floyd Warshall.
Do not explore the adjacent of node if its current cost / weight is lesser than poped cost / weight .
We can optimise our complexity of Dijkstra from O(V2) [Naive]-- > O(E + VlogV) [Priority Queue] – > O(E+V) [Fibonacci Heap , iff we know there is only K types of weights]
But wait, I don’t think in random weighted graph u use Fibonacci heap , because Fibonacci heap is just using 2 queues if u know 0-1 BFS u know we take deque while pushing we check if the cost is 0 then push into front otherwise push into end .
while in fibonaci heap same happens we take 2 queues ( as in graph there is only two types of cost either X or Y ) so we take 2 queues one for push cost X and other for cost Y but fibo heap works when we know there is only K distinct weights but if there are random weights then Dijkistra works fine and implementation is much simpler @spandan_35