17 Jul 2020

Prim vs. Djikstra

  • algorithm
  • leetcode
  • greedy

    • Prim’s algorithm is for finding Minimum Spanning Tree that connects ALL vertices of an undirected weighted graph with the lowest possible sum of its edge weights.

    • only work on undirected graph
    • can handle negative weights


    Djikstra’s algorithm is a greedy algorithm for finding the shortest path between two vertices with the lowest possibel sum of edge weights

    • can work on both directed and undirected graphs
    • cannot handle negative weights
    • O(VlogV)