為什麼叫迪傑斯特拉演算法

A. 解釋一下dijkstra演算法這個計算過程的意思 怎麼算的

最近也看到這個演算法，不過主要是通過C語言介紹的，不太一樣，但基本思想差不多。下面只是我個人的看法不一定準確。
Dijkstra演算法主要解決指定某點(源點)到其他頂點的最短路徑問題。
基本思想：每次找到離源點最近的頂點，然後以該頂點為中心(過渡頂點)，最終找到源點到其餘頂點的最短路。

t=1：令源點(v_0)的標號為永久標號(0,λ)(右上角加點), 其他為臨時(+無窮,λ). 就是說v_0到v_0的距離是0，其他頂點到v_0的距離為+無窮。t=1時，例5.3上面的步驟(2)(3)並不能體現

t=2：第1步v_0(k=0)獲得永久標號，記L_j為頂點標號當前的最短距離(比如v_0標號(0,λ)中L_0=0), 邊(v_k,v_j)的權w_kj. 步驟(2)最關鍵，若v_0與v_j之間存在邊，則比較L_k+w_kj與L_j, 而L_k+w_kj=L_0+w_0j<L_j=+無窮。
這里只有v_1,v_2與v_0存在邊，所以當j=1,2時修改標號, 標號分別為(L_1, v_0)=(1, v_0), (L_2, v_0)=(4, v_0), 其他不變。步驟(3)比較所有臨時標號中L_j最小的頂點, 這里L_1=1最小，v_1獲得永久標號(右上角加點)。

t=3: 第2步中v_1獲得永久標號(k=1), 同第2步一樣，通過例5.3上面的步驟(2)(3)，得到永久標號。 步驟(2),若v_1與v_j(j=2,3,4,5(除去獲得永久標號的頂點))之間存在邊，則比較L_1+w_1j與L_j。這里v_1與v_2，v_3，v_,4存在邊，
對於v_2, L_1+w_12=1+2=3<L_2=4, 把v_2標號修改為(L_1+w_12, v_1)=(3, v_1);
對於v_3, L_1+w_13=1+7=8<L_3=+無窮, 把v_3標號修改為(L_1+w_13, v_1)=(8, v_1);
對於v_4, L_1+w_14=1+5=6<L_4=+無窮, 把v_4標號修改為(L_1+w_14, v_1)=(6, v_1);
v_5與v_1不存在邊，標號不變。步驟(3), 找這些標號L_j最小的頂點，這里v_2標號最小

t=4: k=2, 與v_2存在邊的未獲得永久標號的頂點只有v_4, 比較L_2+w_24=3+1=4<L_4=6, 把v_4標號修改為(L_2+w_24, v_2)=(4, v_2); 其他不變。步驟(3), L_4=4最小。

t=5: k=4, 同理先找v_4鄰接頂點，比較，修改標號，找L_j最小
t=6: 同理

啰嗦的這么多，其實步驟(2)是關鍵，就是通過比較更新最短路徑，右上角標點的就是距離源點最近的頂點，之後每一步就添加一個新的」源點」，再找其他頂點與它的最短距離。

迪傑斯特拉演算法(Dijkstra)(網路)：
http://ke..com/link?url=gc_mamV4z7tpxwqju6BoqxVOZ_josbPNcGKtLYJ5GJsJT6U28koc_#4
裡面有個動圖，更形象地說明了該演算法的過程。(其中每次標注的一個紅色頂點out就和你的這本書中獲得永久標號是相似的)

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

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

C. 迪傑斯特拉演算法的定義

Dijkstra演算法是典型的演算法。Dijkstra演算法是很有代表性的演算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。

D. dijkstra演算法是什麼

Dijkstra演算法是由荷蘭計算機科學家狄克斯特拉（Dijkstra）於1959年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。

其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。

不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。

舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。Dijkstra演算法可以用來找到兩個城市之間的最短路徑。

Dijkstra演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。（u,v)表示從頂點u到v有路徑相連。我們以E所有邊的集合，而邊的權重則由權重函數w: E→[0,∞］定義。

因此，w(u,v)就是從頂點u到頂點v的非負花費值（cost)。邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。

已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑（i.e.最短路徑）。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。

E. 迪傑斯特拉演算法的原理

1.首先，引入一個輔助向量D，它的每個分量 D 表示當前所找到的從起始點 （即源點 ）到其它每個頂點 的長度。
例如，D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這里強調相對就是說在演算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。
2.D的初始狀態為：若從 到 有弧（即從 到 存在連接邊），則D 為弧上的權值（即為從 到 的邊的權值）；否則置D 為∞。
顯然，長度為 D = Min{ D | ∈V } 的路徑就是從 出發到頂點 的長度最短的一條路徑，此路徑為( )。
3.那麼，下一條長度次短的是哪一條呢？也就是找到從源點 到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次於從源點 到頂點 的最短路徑長度。
假設該次短路徑的終點是 ，則可想而知，這條路徑要麼是( )，或者是( )。它的長度或者是從 到 的弧上的權值，或者是D 加上從 到 的弧上的權值。
4.一般情況下，假設S為已求得的從源點 出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為 ）要麼是弧( )，或者是從源點 出發的中間只經過S中的頂點而最後到達頂點 的路徑。
因此，下一條長度次短的的最短路徑長度必是D = Min{ D | ∈V-S }，其中D 要麼是弧( )上的權值，或者是D ( ∈S)和弧( , )上的權值之和。
演算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從 出發的的終點的集合，初始狀態為空集。那麼，從 出發到圖上其餘各頂點 可能達到的長度的初值為D=arcs[Locate Vex(G, )]， ∈V；
2）選擇 ，使得D =Min{ D | ∈V-S } ；
3）修改從 出發的到集合V-S中任一頂點 的最短路徑長度。

F. dijkstra演算法是什麼

dijkstra演算法最短路徑演算法。

Dijkstra是典型最短路徑演算法，用於計算一個節點到其他節點的最短路徑。該演算法使用的是貪心策略：每次都找出剩餘頂點中與源點距離最近的一個頂點。

給定一帶權圖，圖中每條邊的權值是非負的，代表著兩頂點之間的距離。指定圖中的一頂點為源點，找出源點到其它頂點的最短路徑和其長度的問題，即是單源最短路徑問題。

Dijkstra的原理

（1）初始化時，S只含有源節點。

（2）從U中選取一個距離v最小的頂點k加入S中（該選定的距離就是v到k的最短路徑長度）。

（3）以k為新考慮的中間點，修改U中各頂點的距離；若從源節點v到頂點u的距離（經過頂點k）比原來距離（不經過頂點k）短，則修改頂點u的距離值，修改後的距離值是頂點k的距離加上k到u的距離。

G. 蟻群演算法和迪傑斯特拉還有弗洛伊德演算法有什麼區別

蟻群演算法算是屬於人工智慧的搜索演算法。
dijkstra是單源結點最短路徑。效率是o(n^2)
floyd的所有結點的最段路徑。效率是0(n^3)
其實dijkstra就是估價函數為0的一種搜索。
我的了解大概是這樣。