dijkstra演算法貪心證明

1. 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，改培2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題

2. 迪傑斯特拉演算法的本質是貪心還是動態規劃

貪心是一種特殊的動態規劃，動態規劃的本質是獨立的子問題，而貪心則是每次可以找到最優的獨立子問題。
貪心和動歸不是互斥的，而是包含的，貪心更快，但約束更強，適應范圍更小。
動歸和bfs的關系也是一樣的。

展開一點講，在求解最優化問題時，有多個解。而求解的過程類似一個樹，我們稱之為求解樹。

一般的求解樹真的是一棵樹，所以我們只能用bfs來搜索，頂多剪枝。

有些特殊的求解樹，中間很多結點是重合的，結點個數比所有搜索分支的個數少很多個數量級。這類問題較特殊，我們可以保存中間的搜索過程。而記憶化搜索和動態規劃本質上就是一個東西，快就快在可以不用重復計算很多中間結果（所謂的最優子問題）。

還有一些特殊的求解樹，更特殊，它們不止有很多重復結點，而且每次選擇分支的時候，我們可以證明只要選擇一個分支，這個分支的解就一定比其他選擇更優。這類問題就是貪心了，

所以bfs，dp，貪心三個方法都是解決最優化問題的方法，根據問題的不同，約束越大的問題可以用越快的方法，越慢的方法可以解決的問題越普適。

動態規劃的狀態轉移函數，可以抽象成這樣一種函數：

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

其中f就是我們說的獨立問題，每個f都有一個唯一值，也就是沒有後效性。

貪心也是這個函數，但可以證明：

f(xi) >= f(x1|x2|...|xn)

那麼我們就不用再去計算除了f(xi)以外的任何子狀態了，所以就更快

而標準的bfs，雖然也有

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

但是因為對於任意的f(x)，它的子問題f(xi)的輸入狀態xi都不同（換一種思路也可以說f(xi)在不同的路徑下值都不同，本質上是我們怎麼定義xi，到底是狹義的參數還是廣義的狀態），所以無法使用內存去換取時間，就只能去遍歷所有狀態了。