Can we do better , dijkstra-s-algorithm , (Graph Problem 6)

Question link : HERE
My solution : HERE

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.

Help @carre @aneee004

1 Like

@akshitm16 what u did ?

"Made This Topic Public 2 minutes Ago " ?

Sorry, that was my mistake. I made this private conversation by mistake and restored it back. Apologies!

1 Like

Are u moderator ? Nice …then

1 Like

Yes, I was just getting familiar with the actions and clicked on “Make Personal Message” by mistake. Thank you.

1 Like

I don’t think you can do better than that since K logV < V. You can try to optimize but worst case complexity won’t change.

1 Like

can we use floyd warshall algorithm ? ( I don’t know implementation ) , let me solve .

Ok ,thanks I implemented using floyd warshall but it cost me V3 which is far more then K * (E + V logV )

The simple approach of calling Dijkstra on every node, actually turns out to be the optimal solution for this problem.

It is in fact an algorithm of its own, called Johnson’s All Pair Shortest Path Algorithm

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.

After learning dijkstra’s algo , key points -

  1. 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.

  2. Do not explore the adjacent of node if its current cost / weight is lesser than poped cost / weight .

  3. 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]

2 Likes

Thanks for the insights. Especially point 2!

1 Like

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