Ⅰ 最短路徑 | 深入淺出Dijkstra演算法（一）
上次我們介紹了神奇的只有 五行的 Floyd-Warshall 最短路演算法 ，它可以方便的求得 任意兩點的最短路徑， 這稱為 「多源最短路」。
這次來介紹 指定一個點（源點）到其餘各個頂點的最短路徑， 也叫做 「單源最短路徑」。 例如求下圖中的 1 號頂點到 2、3、4、5、6 號頂點的最短路徑。
與 Floyd-Warshall 演算法一樣，這里仍然 使用二維數組 e 來存儲頂點之間邊的關系， 初始值如下。
我們還需要用 一個一維數組 dis 來存儲 1 號頂點到其餘各個頂點的初始路程， 我們可以稱 dis 數組為 「距離表」， 如下。
我們將此時 dis 數組中的值稱為 最短路的「估計值」。
既然是 求 1 號頂點到其餘各個頂點的最短路程， 那就 先找一個離 1 號頂點最近的頂點。
通過數組 dis 可知當前離 1 號頂點最近是 2 號頂點。 當選擇了 2 號頂點後，dis[2]的值就已經從「估計值」變為了「確定值」， 即 1 號頂點到 2 號頂點的最短路程就是當前 dis[2]值。
為什麼呢？你想啊， 目前離 1 號頂點最近的是 2 號頂點，並且這個圖所有的邊都是正數，那麼肯定不可能通過第三個頂點中轉，使得 1 號頂點到 2 號頂點的路程進一步縮短了。 因此 1 號頂點到其它頂點的路程肯定沒有 1 號到 2 號頂點短，對吧 O(∩_∩)O~
既然選了 2 號頂點，接下來再來看 2 號頂點 有哪些 出邊 呢。有 2->3 和 2->4 這兩條邊。
先討論 通過 2->3 這條邊能否讓 1 號頂點到 3 號頂點的路程變短。 也就是說現在來比較 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 號頂點到 3 號頂點的路程，dis[2]+e[2][3]中 dis[2]表示 1 號頂點到 2 號頂點的路程，e[2][3]表示 2->3 這條邊。所以 dis[2]+e[2][3]就表示從 1 號頂點先到 2 號頂點，再通過 2->3 這條邊，到達 3 號頂點的路程。
我們發現 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新為 10。這個過程有個專業術語叫做 「鬆弛」 。即 1 號頂點到 3 號頂點的路程即 dis[3]，通過 2->3 這條邊 鬆弛成功。 這便是 Dijkstra 演算法的主要思想： 通過 「邊」 來鬆弛 1 號頂點到其餘各個頂點的路程。
同理通過 2->4（e[2][4]），可以將 dis[4]的值從 ∞ 鬆弛為 4（dis[4]初始為 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新為 4）。
剛才我們對 2 號頂點所有的出邊進行了鬆弛。鬆弛完畢之後 dis 數組為：
接下來，繼續在剩下的 3、4、5 和 6 號頂點中，選出離 1 號頂點最近的頂點。通過上面更新過 dis 數組，當前離 1 號頂點最近是 4 號頂點。此時，dis[4]的值已經從「估計值」變為了「確定值」。下面繼續對 4 號頂點的所有出邊（4->3，4->5 和 4->6）用剛才的方法進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 3、5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 3 號頂點。此時，dis[3]的值已經從「估計值」變為了「確定值」。對 3 號頂點的所有出邊（3->5）進行鬆弛。鬆弛完畢之後 dis 數組為：
繼續在剩下的 5 和 6 號頂點中，選出離 1 號頂點最近的頂點，這次選擇 5 號頂點。此時，dis[5]的值已經從「估計值」變為了「確定值」。對5號頂點的所有出邊（5->4）進行鬆弛。鬆弛完畢之後 dis 數組為：
最後對 6 號頂點的所有出邊進行鬆弛。因為這個例子中 6 號頂點沒有出邊，因此不用處理。 到此，dis 數組中所有的值都已經從「估計值」變為了「確定值」。
最終 dis 數組如下，這便是 1 號頂點到其餘各個頂點的最短路徑。
OK，現在來總結一下剛才的演算法。 Dijkstra演算法的基本思想是：每次找到離源點（上面例子的源點就是 1 號頂點）最近的一個頂點，然後以該頂點為中心進行擴展，最終得到源點到其餘所有點的最短路徑。
基本步驟如下：
在 博客 中看到兩個比較有趣的問題，也是在學習Dijkstra時，可能會有疑問的問題。
當我們看到上面這個圖的時候，憑借多年對平面幾何的學習，會發現在「三角形ABC」中，滿足不了 構成三角形的條件(任意兩邊之和大於第三邊)。 納尼，那為什麼圖中能那樣子畫？
還是「三角形ABC」，以A為起點，B為終點，如果按照平面幾何的知識， 「兩點之間線段最短」， 那麼，A到B的最短距離就應該是6(線段AB)，但是，實際上A到B的最短距離卻是3+2=5。這又怎麼解釋？
其實，之所以會有上面的疑問，是因為 對邊的權值和邊的長度這兩個概念的混淆， 。之所以這樣畫，也只是為了方便理解（每個人寫草稿的方式不同，你完全可以用別的方式表示，只要便於你理解即可）。
PS：數組實現鄰接表可能較難理解，可以看一下 這里
參考資料：
Dijkstra演算法是一種基於貪心策略的演算法。每次新擴展一個路程最短的點，更新與其相鄰的點的路程。當所有邊權都為正時，由於不會存在一個路程更短的沒擴展過的點，所以這個點的路程永遠不會再被改變，因而保證了演算法的正確性。
根據這個原理， 用Dijkstra演算法求最短路徑的圖不能有負權邊， 因為擴展到負權邊的時候會產生更短的路徑，有可能破壞了已經更新的點路徑不會發生改變的性質。
那麼，有沒有可以求帶負權邊的指定頂點到其餘各個頂點的最短路徑演算法（即「單源最短路徑」問題）呢？答案是有的， Bellman-Ford演算法 就是一種。（我們已經知道了 Floyd-Warshall 可以解決「多源最短路」問題，也要求圖的邊權均為正）
通過 鄰接矩陣 的Dijkstra時間復雜度是 。其中每次找到離 1 號頂點最近的頂點的時間復雜度是 O(N)，這里我們可以用 優先隊列（堆） 來優化，使得這一部分的時間復雜度降低到 。這個我們將在後面討論。
Ⅱ dijkstra用二叉最小堆怎麼用pascal實現
最基本的二叉堆是實現不了的，因為dijkstra要求在運行過程中隨時修改堆內元素，因此要用擴展版的、引入了外部指針的二叉堆
另外，當圖用鄰接表來表示的時候，用二叉堆的時間復雜度為O(ElgV)，不用二叉堆的復雜的是O(V^2);不用鄰接表的時候，用二叉堆時間復雜度為O(V^2lgV)，不用二叉堆的時間復雜度為O(V^2)。也就是說，只有當使用鄰接表來表示稀疏圖的時候，使用二叉堆才有效率優勢。因此本程序使用鄰接表來表示圖
program
SSSP;{single
source
shortest
path}
{假設一個圖的最大節點數為1000，所有運算在integer范圍內}
{程序目標:給定有向圖的鄰接表，求出節點1到節點n的最短路徑長度}
const
maxn=1000;{最大節點數}
var
n:integer;{節點個數}
deg:array[1..maxn]
of
integer;{每個節點的度數}
list:array[1..maxn,1..maxn,1..2]
of
integer;{鄰接表，第一個元素表示邊的中點，第二個元素表示邊的長度}
count:integer;{堆內元素個數計數器}
heap:array[1..maxn]
of
integer;{heap[i]表示堆內的第i的元素的節點編號}
pos:array[1..maxn]
of
integer;{表示編號為i的元素在堆內的位置}
key:array[1..maxn]
of
integer;{表示節點1到節點i的最短距離}
exist:array[1..maxn]
of
boolean;{表示節點i是否存在於堆中}
i,j,now:integer;
procere
swap(var
i,j:integer);{交換整數i和j}
var
temp:integer;
begin
temp:=i;
i:=j;
j:=temp;
end;
procere
heapify(p:integer);{調整堆的過程}
var
best:integer;
begin
best:=p;
if
(p*2<=count)
and
(key[heap[p*2]]<key[heap[best]])
then
best:=p*2;
if
(p*2+1<=count)
and
(key[heap[p*2+1]]<key[heap[best]])
then
best:=p*2+1;
if
best<>p
then
begin
swap(pos[heap[p]],pos[heap[best]]);
swap(heap[p],heap[best]);
heapify(best);
end;
end;
procere
modify(id,new_key:integer);{判斷new_key與key[id]大小，並修改key[id]大小}
var
p:integer;
begin
if
(new_key<key[id])
then
begin
key[id]:=new_key;
p:=pos[id];
while
(p>1)
and
(key[heap[p]]<key[heap[p
div
2]])
do
begin
swap(pos[heap[p]],pos[heap[p
div
2]]);
swap(heap[p],heap[p
div
2]);
p:=p
div
2;
end;
end;
end;
procere
extract(var
id,dis:integer);{讀取堆中最小元素的節點編號和節點1到該節點的距離}
begin
id:=heap[1];
dis:=key[id];
dec(count);
if
(count>0)
then
begin
swap(pos[heap[1]],pos[heap[count+1]]);
swap(heap[1],heap[count+1]);
heapify(1);
end;
end;
begin
{讀取數據}
readln(n);
for
i:=1
to
n
do
begin
read(deg[i]);
for
j:=1
to
deg[i]
do
read(list[i,j,1],list[i,j,2]);
end;
{初始化}
for
i:=1
to
n
do
begin
exist[i]:=true;
pos[i]:=i;
heap[i]:=i;
key[i]:=maxint;
end;
count:=n;
key[1]:=0;
{dijkstra演算法的主要操作}
while
(count>0)
do
begin
extract(i,now);
if
now=maxint
then
break;
for
j:=1
to
deg[i]
do
if
exist[list[i,j,1]]
then
modify(list[i,j,1],now+list[i,j,2]);
end;
{輸出}
if
key[n]=maxint
then
writeln('Not
Connected!'){節點1和節點n不連通}
else
writeln(key[n]);{連通}
end.
Ⅲ 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如果不求任意兩點的最短路徑的話根本沒必要。
Ⅳ 請教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*演算法，以減小最短路徑的搜索范圍。
Ⅳ 用堆來實現計算單源最短路的迪傑斯特拉(Djisktra)演算法
//最近剛寫了這個程序，希望對你有幫助
#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#define MAXNODE 30 //定義最大節點數
#define MAXCOST 1000 //如果兩點間無路勁，則設MAXCOST
int dist[MAXNODE],cost[MAXNODE][MAXNODE],n=6; //為實際節點數
//dijkstra演算法求單源最短路徑，這個函數就沒加註釋了，需要自己理解。
void dijkstra(int v0) //v0為起始節點
{
int s[MAXNODE];
int mindis,dis,i,j,u;
for(i=1;i<=n;i++)
{
dist[i]=cost[v0][i];
s[i]=0;
}
s[v0]=1;
for(i=1;i<=n;i++)
{
mindis=MAXCOST;
for(j=1;j<=n;j++)
{
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=1;j<=n;j++)
if(s[j]==0)
{
dis=dist[u]+cost[u][j];
dist[j]=(dist[j]<dis)?dist[j]:dis;
}
}
}
//自定義display_path函數，輸出各頂點最短路徑
void display_path(int v0)
{
int i;
printf("\n頂點 %d 到各頂點的最短路徑長度如下:\n",v0);
for(i=1;i<=n;i++)
{
printf(" (v%d->v%d):",v0,i);
if(dist[i]==MAXCOST)
printf("無路徑");
else
printf("%d\n",dist[i]);
}
}
//主函數中各個定點的cost值可以根據實際路勁修改
void main()
{
int i,j,v0=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=((i==j)?0:MAXCOST);
cost[1][2]=10;
cost[1][4]=30;
cost[1][5]=100;
cost[1][6]=20;
cost[2][3]=50;
cost[3][5]=10;
cost[4][3]=20;
cost[4][5]=60;
cost[5][6]=30;
dijkstra(v0);
display_path(v0);
}
Ⅵ 程序員開發用到的十大基本演算法
演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。
演算法步驟：
1 從數列中挑出一個元素，稱為 「基準」（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
演算法二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序的平均時間復雜度為Ο(nlogn) 。
演算法步驟：
1.創建一個堆H[0..n-1]
2.把堆首（最大值）和堆尾互換
3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4.重復步驟2，直到堆的尺寸為1
演算法三：歸並排序
歸並排序（Merge sort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
演算法步驟：
演算法四：二分查找演算法
二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜 素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組 為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。
演算法五：BFPRT(線性查找演算法)
BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分 析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜 度，五位演算法作者做了精妙的處理。
演算法步驟：
終止條件：n=1時，返回的即是i小元素。
演算法六：DFS（深度優先搜索）
深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分 支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發 現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。
演算法步驟：
上述描述可能比較抽象，舉個實例：
DFS 在訪問圖中某一起始頂點 v 後，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然後再從 w2 出發，進行類似的訪問，… 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。
接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。
演算法七：BFS(廣度優先搜索)
廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。
演算法步驟：
演算法八：Dijkstra演算法
戴克斯特拉演算法（Dijkstra』s algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。
該演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。
演算法步驟：
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
演算法九：動態規劃演算法
動態規劃（Dynamic programming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。 動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。
動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。 通常許多 子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個 子問題解之時直接查表。 這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。
關於動態規劃最經典的問題當屬背包問題。
演算法步驟：
演算法十：樸素貝葉斯分類演算法
樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下， 如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。
樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言之樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。
盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。
Ⅶ 迪傑斯特拉演算法的演算法實現
· 演算法思想
設給定源點為Vs，S為已求得最短路徑的終點集，開始時令S={Vs} 。當求得第一條最短路徑(Vs ，Vi)後，S為{Vs，Vi} 。根據以下結論可求下一條最短路徑。
設下一條最短路徑終點為Vj ，則Vj只有：
◆ 源點到終點有直接的弧<Vs，Vj>；
◆ 從Vs 出發到Vj 的這條最短路徑所經過的所有中間頂點必定在S中。即只有這條最短路徑的最後一條弧才是從S內某個頂點連接到S外的頂點Vj 。
若定義一個數組dist[n]，其每個dist[i]分量保存從Vs 出發中間只經過集合S中的頂點而到達Vi的所有路徑中長度最小的路徑長度值，則下一條最短路徑的終點Vj必定是不在S中且值最小的頂點，即：
dist[i]=Min{ dist[k]| Vk∈V-S }
利用上述公式就可以依次找出下一條最短路徑。
· 示常式序
· 演算法思想
var a:array[1..100,1..100]of integer;//鄰接矩陣
flag:array[1..100] of boolean;//已經找到最短路徑的節點標志
path:array[1..100]of integer;
w,x,n,i,j,min,minn,k:integer;
begin
readln(n,k);for i:=1 to n do//讀取鄰接矩陣,無路徑寫-1
begin
for j:=1 to n do
begin
read(a[i,j]);
If a[i,j]=-1 then a[I,j]:=maxint;
end;
readln;
end;
fillchar(flag,sizeof(flag),false);//標明所有節點都未找到最短路徑
flag[k]:=true; //源節點除外
fillword(path,sizeof(path) div 2,k);
path[k]:=0;
minn:=k;//標記最小的點for x:=2 to n do
begin
min:=32767;//標記要找下一個最短路徑點的距離
for i:=1 to n do//找下一點點
if (a[k,i]<min) and (flag[i]=false) then
begin
min:=a[k,i];
minn:=i;
end;
flag[minn]:=true;//標記下一個點的找到
for j:=1 to n do //更新最短路徑
if (j<>minn) and (a[k,minn]+a[minn,j]<a[k,j]) and (flag[j]=false) then
begin
a[k,j]:=a[k,minn]+a[minn,j];
path[j]:=minn;
end;
end;
for i:=1 to n do write(a[k,i],' ');//輸出源點到各個點的距離
writeln;
for i:=1 to n do write(path[i],' ');//輸出源點到各個點的距離
end.
求採納（空格被網路吃了……）
Ⅷ 怎樣用DIJKSTRA演算法設計最短路徑
以下................
輸入時，將s,t,x,y,z五個點按照1,2,3,4,5起別名，輸入格式按照下圖例所示
當提示Please enter the vertex where Dijkstra algorithm starts:時輸入演算法的起始點
比如計算結果v1v4v2表示從點1到點2經過1，4，2為最短路徑
Dijkstra演算法的完整實現版本，演算法的源代碼
/* Dijkstra.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex[0]='v';
lin->vertex[1]='0'+temp;
lin->vertex[2]='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:\n");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i<total;i++)
{
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex[1]==now->vertex[1])
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex[1];
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)<searc->cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path[0]='v';
searc->path[1]=now->vertex[1];
searc->path[2]='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost<min)
{
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex[1]-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex[1]-'0')!=start&&p!=NULL)
{
while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("\n%s",p->vertex);
return OK;
}
Ⅸ 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)
Ⅹ djstl演算法
定義Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,
CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
問題描述在無向圖
G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）
編輯本段迪傑斯特拉演算法迪傑斯特拉(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. 對S中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的
距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
編輯本段迪傑斯特拉演算法的原理首先，引進一個輔助向量D，它的每個分量D表示當前所找到的從始點v到每個終點vi的最短路徑的長度。如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調相對就是說在演算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等於最短路徑長度。它的初始狀態為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為
D[j]=Min{D | vi∈V} 的路徑就是從v出發的長度最短的一條最短路徑。此路徑為(v,vj)。
那麼，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。
一般情況下，假設S為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最後到達頂點X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D
| vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。 迪傑斯特拉演算法描述如下：
1）arcs表示弧上的權值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發的最短路徑的終點的集合，初始狀態為空集。那麼，從v出發到圖上其餘各頂點vi可能達到的最短路徑長度的初值為D=arcs[Locate
Vex(G,v),i] vi∈V 2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。
編輯本段迪傑斯特拉演算法C#程序public class Edge
{
public string StartNodeID ;
public string EndNodeID ;
public double Weight ; //權值，代價
} 節點則抽象成Node類，一個節點上掛著以此節點作為起點的「出邊」表。
public class Node
{
private string iD ;
private ArrayList edgeList ;//Edge的集合－－出邊表
public Node(string id )
{
this.iD = id ;
this.edgeList = new ArrayList() ;
}
property#region property
public string ID
{
get
{
return this.iD ;
}
}
public ArrayList EdgeList
{
get
{
return this.edgeList ;
}
}
#endregion
}
在計算的過程中，我們需要記錄到達每一個節點權值最小的路徑，這個抽象可以用PassedPath類來表示：
/// <summary>
/// PassedPath 用於緩存計算過程中的到達某個節點的權值最小的路徑
/// </summary>
public class PassedPath
{
private string curNodeID ;
private bool beProcessed ; //是否已被處理
private double weight ; //累積的權值
private ArrayList passedIDList ; //路徑
public PassedPath(string ID)
{
this.curNodeID = ID ;
this.weight = double.MaxValue ;
this.passedIDList = new ArrayList() ;
this.beProcessed = false ;
}
#region property
public bool BeProcessed
{
get
{
return this.beProcessed ;
}
set
{
this.beProcessed = value ;
}
}
public string CurNodeID
{
get
{
return this.curNodeID ;
}
}
public double Weight
{
get
{
return this.weight ;
}
set
{
this.weight = value ;
}
}
public ArrayList PassedIDList
{
get
{
return this.passedIDList ;
}
}
#endregion
}
另外，還需要一個表PlanCourse來記錄規劃的中間結果，即它管理了每一個節點的PassedPath。
/// <summary>
/// PlanCourse 緩存從源節點到其它任一節點的最小權值路徑=》路徑表
/// </summary>
public class PlanCourse
{
private Hashtable htPassedPath ;
#region ctor
public PlanCourse(ArrayList nodeList ,string originID)
{
this.htPassedPath = new Hashtable() ;
Node originNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
originNode = node ;
}
else
{
PassedPath pPath = new PassedPath(node.ID) ;
this.htPassedPath.Add(node.ID ,pPath) ;
}
}
if(originNode == null)
{
throw new Exception("The origin node is not exist !")
;
}
this.InitializeWeight(originNode) ;
}
private void InitializeWeight(Node originNode)
{
if((originNode.EdgeList == null)
||(originNode.EdgeList.Count == 0))
{
return ;
}
foreach(Edge edge in originNode.EdgeList)
{
PassedPath pPath = this[edge.EndNodeID] ;
if(pPath == null)
{
continue ;
}
pPath.PassedIDList.Add(originNode.ID) ;
pPath.Weight = edge.Weight ;
}
}
#endregion
public PassedPath this[string nodeID]
{
get
{
return (PassedPath)this.htPassedPath[nodeID] ;
}
}
}
在所有的基礎構建好後，路徑規劃演算法就很容易實施了，該演算法主要步驟如下：
(1)用一張表(PlanCourse)記錄源點到任何其它一節點的最小權值，初始化這張表時，如果源點能直通某節點，則權值設為對應的邊的權，否則設為double.MaxValue。
(2)選取沒有被處理並且當前累積權值最小的節點TargetNode，用其邊的可達性來更新到達其它節點的路徑和權值（如果其它節點
經此節點後權值變小則更新，否則不更新），然後標記TargetNode為已處理。
(3)重復(2)，直至所有的可達節點都被處理一遍。
(4)從PlanCourse表中獲取目的點的PassedPath，即為結果。
下面就來看上述步驟的實現，該實現被封裝在RoutePlanner類中：
/// <summary>
/// RoutePlanner 提供圖演算法中常用的路徑規劃功能。
/// 2005.09.06
/// </summary>
public class RoutePlanner
{
public RoutePlanner()
{
}
#region Paln
//獲取權值最小的路徑
public RoutePlanResult Paln(ArrayList nodeList ,string
originID ,string destID)
{
PlanCourse planCourse = new PlanCourse(nodeList
,originID) ;
Node curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;
#region 計算過程
while(curNode != null)
{
PassedPath curPath = planCourse[curNode.ID] ;
foreach(Edge edge in curNode.EdgeList)
{
PassedPath targetPath = planCourse[edge.EndNodeID] ;
double tempWeight = curPath.Weight + edge.Weight ;
if(tempWeight < targetPath.Weight)
{
targetPath.Weight = tempWeight ;
targetPath.PassedIDList.Clear() ;
for(int i=0 ;i<curPath.PassedIDList.Count ;i++)
{
targetPath.PassedIDList.Add(curPath.PassedIDList.ToString())
;
}
targetPath.PassedIDList.Add(curNode.ID) ;
}
}
//標志為已處理
planCourse[curNode.ID].BeProcessed = true ;
//獲取下一個未處理節點
curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;
}
#endregion
//表示規劃結束
return this.GetResult(planCourse ,destID) ;
}
#endregion
#region private method
#region GetResult
//從PlanCourse表中取出目標節點的PassedPath，這個PassedPath即是規劃結果
private RoutePlanResult GetResult(PlanCourse
planCourse ,string destID)
{
PassedPath pPath = planCourse[destID] ;
if(pPath.Weight == int.MaxValue)
{
RoutePlanResult result1 = new RoutePlanResult(null
,int.MaxValue) ;
return result1 ;
}
string[] passedNodeIDs = new
string[pPath.PassedIDList.Count] ;
for(int i=0 ;i<passedNodeIDs.Length ;i++)
{
passedNodeIDs = pPath.PassedIDList.ToString() ;
}
RoutePlanResult result = new
RoutePlanResult(passedNodeIDs ,pPath.Weight) ;
return result ;
}
#endregion
#region GetMinWeightRudeNode
//從PlanCourse取出一個當前累積權值最小，並且沒有被處理過的節點
private Node GetMinWeightRudeNode(PlanCourse
planCourse ,ArrayList nodeList ,string originID)
{
double weight = double.MaxValue ;
Node destNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
continue ;
}
PassedPath pPath = planCourse[node.ID] ;
if(pPath.BeProcessed)
{
continue ;
}
if(pPath.Weight < weight)
{
weight = pPath.Weight ;
destNode = node ;
}
}
return destNode ;
}
#endregion
#endregion
}
編輯本段迪傑斯特拉演算法pascal程序type bool=array[1..10]of
boolean;
arr=array[0..10]of integer;
var a:array[1..10,1..10]of integer;
//存儲圖的鄰接數組，無邊為10000
c,d,e:arr; //c為最短路徑數值,d為各點前趨,
t:bool; //e：路徑，t為輔助數組
i,j,n,m:integer;
inf,outf:text;
////////////////////////////////////////////////////////////////////////////////
procere init; //不同題目鄰接數組建立方式不一樣
begin
assign(inf,'dijkstra.in');
assign(outf,'dijkstra.out');
reset(inf); rewrite(outf);
read(inf,n);
for i:=1 to n do
for j:=1 to n do
begin
read(inf,a[i,j]);
if a[i,j]=0 then a[i,j]:=10000;
end;
end;
////////////////////////////////////////////////////////////////////////////////
procere dijkstra(qi:integer; t:bool; var c{,d}:arr);
//qi起點，{}中為求路徑部
var i,j,k,min:integer; //分,不需求路徑時可以不要
begin //t數組一般在調用前初始
t[qi]:=true; //化成false,也可將部分點
{for i:=1 to n do d[i]:=qi; d[qi]:=0; }
//初始化成true以迴避這些點
for i:=1 to n do c[i]:=a[qi,i];
for i:=1 to n-1 do
begin
min:=10001;
for j:=1 to n do
if (c[j]<min)and(not(t[j])) then begin k:=j;
min:=c[j];end;
t[k]:=true;
for j:=1 to n do
if (c[k]+a[k,j]<c[j])and(not(t[j])) then
begin
c[j]:=c[k]+a[k,j]; {d[j]:=k;}
end;
end;
end;
////////////////////////////////////////////////////////////////////////////////
procere make(zh:integer; d:arr; var e:arr);
//生成路徑,e[0]保存路徑
var i,j,k:integer; //上的節點個數
begin
i:=0;
while d[zh]<>0 do
begin
inc(i);e[i]:=zh;zh:=d[zh];
end;
inc(i);e[i]:=qi; e[0]:=I;
end;
主程序調用：求最短路徑長度：初始化t，然後dijkstra(qi,t,c,d)
求路徑：make(m,d,e) ，m是終點
編輯本段Dijkstra演算法的堆優化(PASCAL實現)一、思考
我們可以發現，在實現步驟時，效率較低(需要O(n)，使總復雜度達到O(n^2)。對此可以考慮用堆這種數據結構進行優化，使此步驟復雜度降為O(log(n))(總復雜度降為O(n
log(n))。
二、實現
1. 將與源點相連的點加入堆，並調整堆。
2. 選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3. 處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4. 若取到的u為終點，結束演算法；否則重復步驟2、3。
三、代碼
procere Dijkstra;
var
u,v,e,i:longint;
begin
fillchar(dis,sizeof(dis),$7e); //距離
fillchar(Inh,sizeof(Inh),false); //是否在堆中
fillchar(visit,sizeof(visit),false); //是否訪問過
size:=0;
e:=last[s];
while e<>0 do //步驟1
begin
u:=other[e];
if not(Inh[u]) then //不在堆里
begin
inc(size);
heap[size]:=u;
dis[u]:=cost[e];
Loc[u]:=size; //Loc數組記錄元素在堆中的位置
Inh[u]:=true;
Shift_up(Loc[u]); //上浮
end
else
if cost[e]<dis[u] then //在堆里
begin
dis[u]:=cost[e];
Shift_up(Loc[u]);
Shift_down(Loc[u]);
end;
e:=pre[e];
end;
visit[s]:=true;
while true do
begin
u:=heap[1]; //步驟2
if u=t then break; //步驟4
visit[u]:=true;
heap[1]:=heap[size];
dec(size);
Shift_down(1);
e:=last[u];
while e<>0 do //步驟3
begin
v:=other[e];
if Not(visit[v]) and (dis[u]+cost[e]<dis[v]) then
//與u相鄰的，未被訪問過的，滿足三角不等式的頂點
if Inh[v] then //在堆中
begin
dis[v]:=dis[u]+cost[e];
Shift_up(Loc[v]);
Shift_Down(Loc[v]);
end
else //不再堆中
begin
inc(size);
heap[size]:=v;
dis[v]:=dis[u]+cost[e];
Loc[v]:=size;
Inh[v]:=true;
Shift_up(Loc[v]);
end;
e:=pre[e];
end;
end;
writeln(dis[t]);
end;
http://ke..com/view/7839.htm
http://ke..com/view/1939816.htm