dijkstra演算法時間復雜度

A. 最短路問題用Dijkstra演算法好還是用遺傳演算法好

dijkstra適合稠密圖，時間復雜度為n^2 或者nlogn+E(堆優化)，但必須保證邊權都為正
spfa 適合稀疏圖，時間復雜度為kE (k為平均每點連接的邊數)

B. johnson演算法是什麼

Johnson演算法適用於求All
Pairs
Shortest
Path.
Johnson演算法應用了重標號技術，先進行一次Bellman-Ford演算法，然後對原圖進行重標號，w'(i,j)=h[i]-h[j]+w(i,j)。然後對每個點進行一次Dijkstra，每次Dijkstra的復雜度為O(nlogn+m)，於是演算法復雜度為O(n^2logn+m)。
關於求解流水作業調度問題的
Johnson
演算法具體描述:

C. Dijkstra演算法的堆優化

>>全國交通咨詢？
作為一個OIer、我表示對最短路徑演算法稍有研究。
Dijkstra和Floyd是按需要來看的
首先
dijkstra求的是從一個節點到其他節點的最短路 時間復雜度不優化的情況下是n方
Floyd求的是任意兩點間的最短路徑、時間復雜度永遠是n的立方、而且我表示除了鄰接矩陣我再沒用其他數據結構寫過。
所以在處理很多的結點很多邊的時候、Floyd又耗費時間又浪費空間、沒有特殊需要不要用。
至於dijkstra、在稀疏圖里它一定比SPFA快
>>SPFA是另一種最短路演算法、是Bellman-Ford的隊列優化
但是對於稠密圖、SPFA要比dijkstra快很多。
但是、dijkstra可以用堆優化
用小根堆來維護dijkstra中的dist數組、在每次取最小值的時候取堆頂元素
這樣時間復雜度是nlogn級、很快
至於SPFA跟Heapdijkstra哪個快這個不大好比較= =、

OTZ回答的有點跑偏了。
注意最開始的那幾行
我強烈推薦dijkstra、Floyd如果不求任意兩點的最短路徑的話根本沒必要。

D. 數據結構之圖：求所有節點之間的最短路徑，用什麼演算法時間復雜度小求答案與解釋

兩者時間復雜度一般都是O(n3)，但對於稀疏圖來說重復使用Dijkstra方法比較好！
Dijkstra演算法時間復雜度為O（V*V+E）,可以用優先隊列進行優化，優化後時間復雜
度變為0（v*lgn）。
源點可達的話，O（V*lgV+E*lgV）=>O（E*lgV）。
當是稀疏圖的情況時，此時E=V*V/lgV，所以演算法的時間復雜度可為O（V^2） 。可以用優先隊列進行優化，優化後時間復雜度變為0（v*lgn）。
具體詳細解釋你可以看看這個http://blog.chinaunix.net/uid-27164517-id-3287891.html。

E. 請教Dijkstra演算法的時間復雜度

行2--4的初始化對n個頂點進行，顯然是O（n）5--6行O（1）7行n個頂點入隊列O（n） 8行--14行，從8行可以看出進行了n遍循環，每遍在第九行調用一次ExtractMin過程，ExtractMin過程需要搜尋鄰接表，每一次需要搜尋整個數組，所以一次操作時間是O(n);11行到14行對節點u的鄰接表中的邊進行檢查，總共有|E|次（總共.每條邊最多檢查一次)，因此是O(E)；合起來就是O（E+n*n） = O（n^2);以上合起來就是O（n）+O（1）+O（n）+O（n^2） == O（n^2).就這樣

F. 利用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）。

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

G. 怎樣用動態規劃法求單源最短路徑

int[] cost=new int[n];//cost[i]存儲i到n-1的子問題的最短路徑值
int[] path=new int[n];//path[i]存儲狀態，使cij+cost[i]最小的j值
//對數組cost[n]和path[n]進行初始化
for(int i=0;i<n-1;i++){
cost[i]=Integer.MAX_VALUE;
path[i]=-1;
}
cost[9]=0;
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>=i;j--){
//得到i的鄰接點
if(c[i][j]<Integer.MAX_VALUE&&cost[i]>(c[i][j]+cost[j])){

cost[i]=c[i][j]+cost[j];
path[i]=j;
}
}
}
System.out.println("最短路徑為："+cost[0]);
int i=0;
System.out.print("0");
while(i!=n-1){
System.out.print("-->"+path[i]);
i=path[i];

H. 圖論中常見的最短路徑演算法有幾種都是什麼

主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、

I. 請教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*演算法，以減小最短路徑的搜索范圍。

J. Dijkstra演算法問題

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