A question about Dijkstra's cheapest flights analysis

[sidazhang]

https://github.com/kamyu104/LeetCode-Solutions/blob/master/Python/cheapest-flights-within-k-stops.py

The time analysis indicates O((|E| + |V|) * log|V|).

The typical Dijkstra's analysis involves the following:

1. You visit each vertex once. Therefore, the priority queue is up to V. So each heap operation is O(log(V))
2. You visit all the edge once and each time involves an heap operation. So E log(V)
3. Eventually, you remove all V from the heap. And so V log (V)

This leaves us with (E + V)log(V) for a normal dijkstra's.

In your solution, your best cache is on both vertex and k. Which means you can visit each vertex up to K times.

So the analysis should be O(K(E + V)log(KV)) which should be ~ O(KE*LOG(V))

[kamyu104]

Yes, if K is not counted in E and V. It will be O(K(E + V)log(KV)).