dijkstra演算法圖解

1. Dijkstra演算法流程圖

定義G=(V,E)，定義集合S存放已經找到最短路徑的頂點，集合T存放當前還未找到最短路徑的頂點，即有T=V-S

Dijkstra演算法描述如下：

(1) 假設用帶權的鄰接矩陣edges來表示帶權有向圖，edges[i][j]表示弧<Vi, Vj>上的權值。若<Vi, Vj>不存在則置edges[i][j]=∞（計算機上用一個允許的最大值代替）。S為已經找到的從Vs出發的最短路徑的終點集合，它初始化為空集。那麼，從Vs出發到圖上其餘各頂點（終點）Vi可能達到的最短路徑長度的初值為：D[i]=deges[s][i] Vi∈V

(2) 選擇Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是當前求得的一條從Vs出發的最短路徑的終點。令S=S∪{Vj}

(3) 修改從Vs出發到集合V-S上任一頂點Vk可達的最短路徑長度。如果D[j]+edges[j][k]<D[k]則修改D[k]為D[k]=D[j]+edges[j][k]

重復操作(2)(3)共n-1次。由此求得從Vs到圖上其餘各頂點的最短路徑。

2. 利用Dijkstra演算法求下圖中從頂點1到其它各頂點間的最短路徑，按下面表格形式

v1到v2：10為最短路徑；

v1到v3：7為最短路徑；

v1到v4：8為最短路徑；

v1到v5：v1-> v2 -> v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15為最短路徑；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13為最短路徑；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35為最短路徑

Dijkstra：

求單源、無負權的最短路。時效性較好，時間復雜度為O（V*V+E）。源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2）。若是斐波那契堆作優先隊列的話，演算法時間復雜度，則為O（V*lgV + E）。

以上內容參考：網路-最短路徑演算法

3. 迪傑斯特拉演算法的演算法思想

按路徑長度遞增次序產生演算法：
把頂點集合V分成兩組：
（1）S：已求出的頂點的集合（初始時只含有源點V0）
（2）V-S=T：尚未確定的頂點集合
將T中頂點按遞增的次序加入到S中，保證：
（1）從源點V0到S中其他各頂點的長度都不大於從V0到T中任何頂點的最短路徑長度
（2）每個頂點對應一個距離值
S中頂點：從V0到此頂點的長度
T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度
依據：可以證明V0到T中頂點Vk的，或是從V0到Vk的直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和
（反證法可證）
求最短路徑步驟
演算法步驟如下：
G={V,E}
1. 初始時令 S={V0},T=V-S={其餘頂點}，T中頂點對應的距離值
若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>，d(V0,Vi)為∞
2. 從T中選取一個與S中頂點有關聯邊且權值最小的頂點W，加入到S中
3. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

4. 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到任何其他頂點的最短路徑。

5. dijkstra演算法

樓上正解，你找個圖自己用此演算法實踐一下就知道了，從A點出發，發現離A最近的點是B點，那麼我們就已經認為A到B的最短距離就是AB了，如果有負數，就指不定冒出個C點,AC+CB<AB;或者冒出個DE為很大的負值，AC+CD+DE+EF+FB<AB;等等諸如此類的情況。
簡單說來，你駕車從家出發到某地沿某條路只需經過一個收費站，但是遠在外省某地有個站不但不收你的費，你去了還會給你個千八百萬的歡迎光臨費，你能說你直接沿著這條路去某地是最省費用的？不計時間成本，繞到外省那個給你錢的地方，再繞回到你的目的地，還能賺錢呢。
而且一般權值為負的圖研究也比較少。有些帶負權的圖，某些點間還沒有最小距離呢。中間出個帶某條負權很大的邊的環圈，繞此一圈所經過的距離反而減少了，那就一直在此圈上繞啊繞啊繞到負的足夠大溢出為止。
當然考慮各種自己隨便假設出來的變種問題也是很有趣的。比如說邊帶有多個權值對應多次經過改變的消費，上面的問題有可能變成有解的。話說那個站會後悔，第二次經過它會收回100萬，第三次經過收回250萬，這樣的話你只需要經過一次就夠了，問題也是有解的。再比如說對於多權重圖，從A點出發經過B點到達C點的最短路線，就不是簡單的AB最短路線+BC最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^

6. Dijkstrath演算法是什麼如何用Dijkstrath演算法求計算機網路拓撲圖的最短路徑

Dijkstra演算法是典型 的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
迪傑斯特拉(Dijkstra)演算法思想
按路徑長度遞增次序產生最短路徑演算法：

把V分成兩組：

（1）S：已求出最短路徑的頂點的集合

（2）V-S=T：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑遞增的次序加入到S中，

保證：（1）從源點V0到S中各頂點的最短路徑長度都不大於

從V0到T中任何頂點的最短路徑長度

（2）每個頂點對應一個距離值

S中頂點：從V0到此頂點的最短路徑長度

T中頂點：從V0到此頂點的只包括S中頂點作中間

頂點的最短路徑長度

依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的

直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和

（反證法可證）

求最短路徑步驟
演算法步驟如下：

1. 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∝

2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的

距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

7. dijkstra演算法有哪些

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑，該演算法按照最短路徑長度遞增的順序產生所以最短路徑。

對於圖G=（V，E），將圖中的頂點分成兩組：

第一組S：已求出的最短路徑的終點集合（開始為{v0}）。

第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

演算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。

(7)dijkstra演算法圖解擴展閱讀：

從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，並且把該點加入到T中，此時完成一個頂點，需要看看新加入的頂點是否可以到達其他頂點並且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那麼就替換這些頂點在dis中的值。 然後，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

8. 實現Dijkstra演算法，並用圖形化的方式顯示出該演算法的運算過程。

一般數據結構書上都會有
const int NumVertices=10 //假定最大10個頂點

class Gragh 圖類定義（鄰接矩陣表示）
{
private:
float Edge[NumVertices][NumVertices];
//鄰接矩陣表示
float dist[NumVertices];
//頂點0到其他個頂點最短路徑長度
int path[NumVertices];
//最短路徑上該頂點的前一個頂點號,
int S[Numvertices];
/*已求得最短路徑上頂點的頂點號，=1表示已經得 最短路徑=0表示為未求得最短路徑*/
public:
void Shortestpath(int ,int );//Dijkstra演算法
int choose(int);
};

void Graph::Shortestpath(int n,int v)
{ //n是圖的頂點數，v為所要求的頂點
for(int i=0,i<n;i++)
{//dist，path，S數組初始化
dist[i]=Edge[v][i];
S[i]=0;
if(i!=v&&dist[i]<MAXNUM)path[i]=v;
else path[i]=-1;
}
S[v]=1;dist[v]=0//v是起始頂點
for(i=0;i<n-1;i++)
{//從v確定n-1條路徑
float min=MAXNUM;
int u=v;
for(int j=0;j<n;j++)
{//選擇不在S中有最短路徑的頂點u
if(!S[j]&&dist[j]<min)
{
u=j;min=dist[j];
}
S[u]=1;//頂點u加入S集合中
for(int w=0;w<n;w++)
if(!S[w]&&Edge[u][w]<MAXNUM&&
dist[u]+Edge[u][w]<dist[w])
{/*修改不在S中的其他頂點的當前最短路徑*/
dist[w]=dist[u]+Edge[u][w];
path[w]=u;
}
}
}

9. 解釋一下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就和你的這本書中獲得永久標號是相似的)