刷題心得—MST和SPT

本篇随筆淺談一下MST和SPT的差別。

其實很簡單。

MST是最小生成樹，它是一張圖的生成樹，其中邊權和最小的一種生成樹。

而SPT是最短路徑樹。它是一張圖的生成樹，其中保證根為源點，并且源點到所有節點的路徑都是源點到所有節點的最短路。

其實是不一樣的。

SPT不一定是MST，MST也不一定是SPT，這是兩種東西。

注意，慎重。