dijkstra演算法

『壹』 dijkstra演算法復雜度是多少

1、簡單復雜度是O(n2)。

Dijkstra 演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合 Q，所以搜索 Q 中最小元素的運算（Extract-Min(Q)）只需要線性搜索 Q 中的所有元素。這樣的話演算法的運行時間是 O(n2)。
附演算法：

1functionDijkstra(G,w,s)
2foreachvertexvinV[G]
3d[v]:=infinity
4previous[v]:=undefined
5d[s]:=0
6S:=emptyset
7Q:=setofallvertices
8whileQisnotanemptyset
9u:=Extract_Min(Q)
10S:=Sunion{u}
11foreachedge(u,v)outgoingfromu
12ifd[v]>d[u]+w(u,v)
13d[v]:=d[u]+w(u,v)
14previous[v]:=u

O（n）+O（1）+O（n）+O（n^2） == O（n^2).

2、用堆優化後的時間復雜度：O((m+n)log n)

『貳』 Dijkstra演算法時間復雜度

我們可以用大O符號將Dijkstra演算法的運行時間表示為邊數m和頂點數n的函數。

Dijkstra演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q,所以搜索Q中最小元素的運算(Extract-Min(Q))只需要線性搜索Q中的所有元素。這樣的話演算法的運行時間是O(n2)。

對於邊數少於n2稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra演算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點(Extract-Min)。當用到二叉堆的時候，演算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓演算法運行時間達到O(m + n log n)。相關問題和演算法

在Dijkstra演算法的基礎上作一些改動，可以擴展其功能。例如，有時希望在求得最短路徑的基礎上再列出一些次短的路徑。為此，可先在原圖上計算出最短路徑，然後從圖中刪去該路徑中的某一條邊，在餘下的子圖中重新計算最短路徑。對於原最短路徑中的每一條邊，均可求得一條刪去該邊後子圖的最短路徑，這些路徑經排序後即為原圖的一系列次短路徑。

OSPF（open shortest path first, 開放最短路徑優先）演算法是Dijkstra演算法在網路路由中的一個具體實現。
與Dijkstra演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。

與最短路徑問題有關的一個問題是旅行商問題(traveling salesman problem)，它要求找出通過所有頂點恰好一次且最終回到源點的最短路徑。該問題是NP難的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間演算法。

如果有已知信息可用來估計某一點到目標點的距離，則可改用A*演算法，以減小最短路徑的搜索范圍。

『叄』 Prim演算法和Dijkstra演算法的異同

所謂距離矢量即是將一條路由信息考慮成一個由目標和距離（用 Metric 來度量）組稱的矢量，每一台路由器從其鄰居處獲得路由信息，並在每一條路由信息上疊加從自己到這個鄰居的距離矢量，從而形成自己的路由信息。 在一個鏈路狀態路由選擇中，一個結點檢查所有直接鏈路的狀態，並將所得的狀態信息發送給網上所有的其他的結點，而不僅僅是發給那些直接相連的結點。每個節點都用這種方式，所有其他的結點從網上接收包含直接鏈路狀態的路由信息。 每當鏈路狀態報報文到達時，路由結點便使用這些狀態信息去更新自己的網路拓撲和狀態「視野圖」，一旦鏈路狀態發生改變，結點對跟新的網路圖利用Dijkstra最短路徑演算法重新計算路由，從單一的報源發出計算到達所有的結點的最短路徑。 看明白了么？ 最簡單理解。。距離矢量演算法是靜態的。。。鏈路狀態路由演算法是動態的，，隨時改變的。。 距離矢量演算法，一旦相鄰節點發生故障，傳輸就出終止； 鏈路狀態路由演算法，一旦相鄰的一個節點發生故障，會自動轉移數據包到另外的節點進行傳輸過程。

『肆』 Dijkstra演算法問題

dijkstra演算法的時間復雜度是O(n²),
不妨設為kn²,其中次數小於1的項忽略
k(10×10）=10ms
那麼k(40×40）=16[k×（10×10）]=160ms

『伍』 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最短路線了，說不定兩者有重合邊，第二次經過來個天價就傻眼了。其實這種圖貌似應該可以轉化成單權重圖的，我直覺估計啊，剛隨便想出這個問題，還沒去思考這個問題的解^_^

『陸』 Dijkstra演算法

這是我自己寫的一個簡單的DIJKSTRA演算法，其中測試數據是
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
結構清晰簡單，對於你要搞懂這個演算法很有幫助。有不懂的可以問我：我的QQ是396730783
#include"stdio.h"
#define MAX 100000000
int main()
{
int map[101][101];
int dis[101];
int a,b,c;
int i,j,k,n,m;
int min;
while(scanf("%d",&n)==1)
{
int final[101] = {0};
scanf("%d",&m);
for(i=0;i<n;i++)
for(j=i;j<n;j++)
{
map[i][j] = map[j][i] = MAX;
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b] = c;
}
for(i=1;i<n;i++)
{
dis[i] = map[0][i];
}
dis[0] = 0;
final[0] = 1;
for(i=0;i<n-1;i++)
{
min = MAX;
for(j=1;j<n;j++)
{
if(!final[j] && min > dis[j])
{
min = dis[j];
k = j;
}
}
final[k]=1;
for(j=1;j<n;j++)
{
if(!final[j] && dis[k]+map[k][j]<dis[j])
dis[j] = dis[k]+map[k][j];
}
}
for(i=1;i<n;i++)
{
if(dis[i] == MAX)
printf("不可通");
else
printf("%5d",dis[i]);
}
printf("\n");

}
return 0;

}

『柒』 folyd與dijkstra演算法比較

floyd是所有頂點間距離、dijkstra是單頂點到別的所有頂點距離
floyd演算法權值可以小於0，dijkstra演算法權值不得小於0
floyd演算法是動態規劃、dijkstra是貪心法
floyd是O(n^3)，dijkstra演算法是 O(n^2)

『捌』 比較Dijkstra演算法與Floyd演算法。

（1）Dijkstra演算法：在網路中用得多，一個一個節點添加，加一個點刷一次路由表。

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

（2）Floyd演算法：把所有已經連接的路徑都標出來，再通過不等式比較來更改路徑。

Floyd演算法又稱為插點法，是一種用於尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

『玖』 dijkstra演算法是什麼

迪傑斯特拉演算法用於求解一個有向圖（也可以是無向圖，無向圖是有向圖的一種特例）的一個點（稱之為原點）到其餘各點（稱之為周邊點）的最短路徑問題。演算法構思很是巧妙（我這么認為），簡直達到了「無心插柳柳成蔭」的境界。演算法本身並不是按照我們的思維習慣——求解從原點到第一個點的最短路徑，再到第二個點的最短路徑，直至最後求解完成到第n個點的最短路徑，而是求解從原點出發的各有向路徑的從小到大的排列（如果這個有向圖中有環1-2-3-1演算法豈不是永無終結之日了？？！！），但是演算法最終確實得到了從原點到圖中其餘各點的最短路徑，可以說這是個副產品，對於演算法的終結條件也應該以求得了原點到圖中其餘各點的最短路徑為宜。清楚了演算法的這種巧妙構思後，理解演算法本身就不是難題了。

演算法把一個圖（G）中的點劃分成了若幹部分：

1）：原點（v）；

2）：所有周邊點（C）；

另外有一個輔助集合S，從v到S中的點的最短路徑已經求得。S的最初狀態是空集。

這樣就可以進一步劃分圖（G）：

1）：原點（v）；

2）：已求出v至其最短路徑的周邊點（S）；

3）：尚未求出v至其最短路徑的周邊點（Other=C-S）；

演算法的主體思想：

A、找到v——Other所有路徑中的的最短路徑vd=v——d（Other的一個元素）；

B、找到v——S——Other所有路徑中的的最短路徑vi=v——i（Other的一個元素）；

C、比較vd和vi如果vd<=vi則將d加入S且從Other中刪除，否則將i加入S且從Other中刪除。

重復以上步驟直至Other為空集。

我們求得的最短路徑是升序排列的，那為什麼下一條最短路徑就存在於v——

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