貪心演算法dijkstra

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

貪心是一種特殊的動態規劃，動態規劃的本質是獨立的子問題，而貪心則是每次可以找到最優的獨立子問題。
貪心和動歸不是互斥的，而是包含的，貪心更快，但約束更強，適應范圍更小。
動歸和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，到底是狹義的參數還是廣義的狀態），所以無法使用內存去換取時間，就只能去遍歷所有狀態了。

❷ dijx是什麼意思

Dijkstra演算法是荷蘭計算機科學家Edsger W. Dijkstra於1956年提出的，是一種解決單源最短路徑問題的貪心演算法。它通過優先隊列來存儲和訪問每個頂點的距離，從而快速找到最短路徑。該演算法廣泛應用於地圖應用、交通路線計算、圖形文件路徑查找和網路路由演算法等領域。在實際應用中，Dijkstra演算法可以通過堆優化或隊列優化實現，以降低時間復雜度並提高演算法效率。

❸ Dijkstra演算法

迪傑斯特拉演算法（Dijkstra）是由荷蘭計算機科學家狄克斯特拉在1959年提出的。它是一種求解有權圖中最短路徑的演算法，主要特點是採用貪心演算法的策略，從起始點開始，每次遍歷到距離始點最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止。

迪傑斯特拉演算法求的是單源最短路問題。其實現過程如下：

示例中我們可以發現，這里的迪傑斯特拉演算法只適用於邊權均為正的圖。Dijkstra模板題如下：

給定一個有n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。請你求出1號點到n號點的最短距離，如果無法從1號點走到n號點，則輸出-1。輸入格式：第一行包含整數n和m。接下來m行每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z。輸出格式：輸出一個整數，表示1號點到n號點的最短距離。如果路徑不存在，則輸出-1。數據范圍：[公式]，[公式]，圖中涉及邊長均不超過10000。輸入樣例：3 3 1 2 2 2 3 1 1 3 4 輸出樣例：3

分析：由本題的點和邊的數據范圍可知，這是一個稠密圖，因此使用鄰接矩陣來存儲圖。（樸素Dijkstra正是用來處理稠密圖的）注意：本題有重邊和自環。由於邊權為正，所以自環一定不會在最短路中。而對於重邊，我們存下最短邊即可。

代碼實現：時間復雜度為[公式]。對於稀疏圖（m與n數據范圍接近時），Dijkstra還有另外一種形式：堆優化Dijkstra。優化主要在尋找距離最小的點的操作上。堆有兩種實現方式，之前已經有寫過手寫堆，這里使用另外一種堆的實現方式：優先隊列。由於是稀疏圖，存儲方式需要改成鄰接表形式。其思路和樸素Dijkstra一致。

代碼實現：時間復雜度為[公式]。

以上就是樸素Dijkstra演算法和堆優化Dijkstra演算法。都是用於單源正權邊最短路。未必優化版的就是更好的，樸素版適合稠密度，堆優化版適合稀疏圖。