Dijkstra & Union Find

Dijkstra

Problem: given a weighted graph of non-negative weight, and a source node s, find shortest path from s to all other nodes.

• run time: O(nlogn+mlogn). Because m >> n => ~O(mlogn)

  • n is number of node
  • m is number of edge

• Space: O(n+m) for adjacent list, O(n) for heap => O(n+m)

Union Find