Understanding Time complexity calculation for Dijkstra Algorithm

Dijkstra’s shortest path algorithm is O(ElogV) where:

  • V is the number of vertices
  • E is the total number of edges

Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV) where:

  • V is the number of vertices
  • E is the maximum number of edges attached to a single node.

Let’s rename your E to N. So one analysis says O(ElogV) and another says O(VNlogV). Both are correct and in fact E = O(VN). The difference is that ElogV is a tighter estimation.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)