dijkstra演算法csdn

❶ dijkstra演算法是什麼

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

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

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

Dijkstra的原理

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

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

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

❷ Dijkstra 演算法是什麼 Dijkstra 在哪裡用

迪傑斯特拉演算法用來解決從頂點v0出發到其餘頂點的最短路徑,該演算法按照最短路徑長度遞增的順序產生所以最短路徑.
對於圖G=（V,E）,將圖中的頂點分成兩組：
第一組S：已求出的最短路徑的終點集合（開始為{v0}）.
第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）.
演算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中,直到所有頂點都被加入到第一組頂點集S為止.
【演算法思想】
g為用鄰接矩陣表示的帶權圖.
（1）S

❸ 用dijkstra演算法求a到f的最短路徑

#include<stdio.h>
inta[205][205];//記錄鄰接矩陣
intdist[205];//到每個點的最短路
intm,n;//m條路，n個點
constintINF=0xfffffff;
voidinit()//初始化數據
{
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
a[i][j]=(i==j?0:INF);
}

voiddijkstra(intu)//從第u個點開始走
{
intsign[205]={0};//標記走過否
intx=u;
inti,j;
for(i=0;i<n;i++)//初始化到各點距離
dist[i]=a[x][i];
dist[x]=0;//到本身距離為0
sign[x]=1;//改點以走過
for(i=1;i<=n-2;i++)
{
intmin=INF;
for(j=0;j<n;j++)//在為走過的點中取距離x最短的點
{
if(!sign[j]&&min>dist[j])
{
min=dist[j];
x=j;
}
}
sign[x]=1;//標記，已走過

for(j=0;j<n;j++)//x以改變，更新dist[]值
{
if(!sign[j]&&dist[x]+a[x][j]<dist[j]&&a[x][j]<INF)
dist[j]=a[x][j]+dist[x];
}
}
}
intmain()
{
inti;
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=0;i<m;i++)
{
intx,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z<a[x][y])//取兩點多條路最小路
a[x][y]=z;
if(z<a[y][x])
a[y][x]=z;
}
ints,t;
scanf("%d%d",&s,&t);
dijkstra(s);

if(dist[t]<2000000)
printf("%d
",dist[t]);
else
printf("-1
");
}
return0;
}

參考鏈接 ：http://blog.csdn.net/ouyangying123/article/details/38706957

❹ 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演算法有哪些

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

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

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

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

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

(5)dijkstra演算法csdn擴展閱讀：

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

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

❼ 圖遍歷演算法之最短路徑Dijkstra演算法

最短路徑問題是圖論研究中一個經典演算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，演算法的具體形式包括：

常用的最短路徑演算法包括：Dijkstra演算法，A 演算法，Bellman-Ford演算法，SPFA演算法（Bellman-Ford演算法的改進版本），Floyd-Warshall演算法，Johnson演算法以及Bi-direction BFS演算法。本文將重點介紹Dijkstra演算法的原理以及實現。

Dijkstra演算法，翻譯作戴克斯特拉演算法或迪傑斯特拉演算法，於1956年由荷蘭計算機科學家艾茲赫爾.戴克斯特拉提出，用於解決賦權有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節點到圖中任意節點的最短路徑，演算法可用於尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖 中， 為圖節點的集合， 為節點之間連線邊的集合。假設每條邊 的權重為 ，找到由頂點 到其餘各個節點的最短路徑（單源最短路徑）。

為帶權無向圖，圖中頂點 分為兩組，第一組為已求出最短路徑的頂點集合（用 表示）。初始時 只有源點，當求得一條最短路徑時，便將新增頂點添加進 ，直到所有頂點加入 中，演算法結束。第二組為未確定最短路徑頂點集合（用 表示），隨著 中頂點增加， 中頂點逐漸減少。

以下圖為例，對Dijkstra演算法的工作流程進行演示（以頂點 為起點）：

註：
01） 是已計算出最短路徑的頂點集合；
02） 是未計算出最短路徑的頂點集合；
03） 表示頂點 到頂點 的最短距離為3
第1步 ：選取頂點 添加進

第2步 ：選取頂點 添加進 ，更新 中頂點最短距離

第3步 ：選取頂點 添加進 ，更新 中頂點最短距離

第4步 ：選取頂點 添加進 ，更新 中頂點最短距離

第5步 ：選取頂點 添加進 ，更新 中頂點最短距離

第6步 ：選取頂點 添加進 ，更新 中頂點最短距離

第7步 ：選取頂點 添加進 ，更新 中頂點最短距離

示例：node編號1-7分別代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結果：

示例：

找到D（4）到G（7）的最短路徑：

[1] 維基網路，最短路徑問題： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra演算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

❽ 最短路徑 | 深入淺出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演算法這個計算過程的意思 怎麼算的

最近也看到這個演算法，不過主要是通過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就和你的這本書中獲得永久標號是相似的)

❿ dijkstra演算法

[問題分析]
對於一個含有n個頂點和e條邊的圖來說，從某一個頂點Vi到其餘任一頂點Vj的最短路徑，可能是它們之間的邊（Vi，Vj），也可能是經過k個中間頂點和k+1條邊所形成的路徑(1≤k≤n-2)。下面給出解決這個問題的Dijkstra演算法思想。
設圖G用鄰接矩陣的方式存儲在GA中，GA[i,j]=maxint表示Vi，Vj是不關聯的，否則為權值（大於0的實數）。設集合S用來保存已求得最短路徑的終點序號，初始時S=[Vi]表示只有源點，以後每求出一個終點Vj，就把它加入到集合中並作為新考慮的中間頂點。設數組dist[1..n]用來存儲當前求得的最短路徑，初始時Vi，Vj如果是關聯的，則dist[j]等於權值，否則等於maxint，以後隨著新考慮的中間頂點越來越多，dist[j]可能越來越小。再設一個與dist對應的數組path[1..n]用來存放當前最短路徑的邊，初始時為Vi到Vj的邊，如果不存在邊則為空。
執行時，先從S以外的頂點（即待求出最短路徑的終點）所對應的dist數組元素中，找出其值最小的元素（假設為dist[m]），該元素值就是從源點Vi到終點Vm的最短路徑長度，對應的path[m]中的頂點或邊的序列即為最短路徑。接著把Vm並入集合S中，然後以Vm作為新考慮的中間頂點，對S以外的每個頂點Vj，比較dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中間頂點後可以得到更好的方案，即可求得更短的路徑，則用它代替dist[j]，同時把Vj或邊（Vm，Vj）並入到path[j]中。重復以上過程n-2次，即可在dist數組中得到從源點到其餘各終點的最段路徑長度，對應的path數組中保存著相應的最段路徑。

下面給出具體的Dijkstra演算法框架（註：為了實現上的方便，用一個一維數組s[1..n]代替集合S，用來保存已求得最短路徑的終點集合，即如果s[j]=0表示頂點Vj不在集合中，反之，s[j]=1表示頂點Vj已在集合中）。
Procere Dijkstra(GA,dist,path,i)；
{表示求Vi到圖G中其餘頂點的最短路徑，GA為圖G的鄰接矩陣，dist和path為變數型參數，
其中path的基類型為集合}
Begin
For j:=1 To n Do Begin {初始化}
If j<>i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j]<maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]；
End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k個終點Vm}
If (s[j]=0) and (dist[j]<w) Then Begin m:=j；w:=dist[j]； End；
If m<>i Then s[m]:=1 else exit；
{若條件成立，則把Vm加入到S中，
否則退出循環，因為剩餘的終點，其最短路徑長度均為maxint，無需再計算下去}
For j:=1 To n Do {對s[j]=0的更優元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j]<dist[j])
Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；

（1）從一個頂點到其餘各頂點的最短路徑
對於一個含有n個頂點和e條邊的圖來說，從某個頂點vi到其餘任一頂點vj的最短路徑，可能是它們之間的邊（vi，vj），也可能是經過k個中間點和k+1條邊所形成的路徑（1≤k ≤n-2）。
首先來分析Dijkstra的演算法思想
設圖G用鄰接矩陣的方式存儲在GA中，GA[I，j]=maxint表示vi，vj是不關聯的，否則為權值（大於0的實數）。設集合S用來存儲保存已求得最短路徑的終點序號，初始時S=[vi]表示只有源點，以後每求出一個終點vj，就把它加入到集合中並作為新考慮的中間頂點。設數組dist[1..n]用來存儲當前求得的最短路徑，初始時vi，vj如果是關聯的，則dist[j]等於權值，否則等於maxint，以後隨著新考慮的中間頂點越來越多，dist[j]可能越來越小。再設一個與dist對應的數組path[1..n]用來存放當前最短路徑的邊，初始時vi到vj的邊，如果不存在邊則為空。
執行時，先從S以外的頂點（即待求出最短路徑的終點）所對應的dist數組元素中，找出其值最小的元素（假設為dist[m]），該元素值就是從源點vi到終點vm的最短路徑長度，對應的path[m]中的頂點或邊的序列即為最短路徑。接著把vm並入集合S中，然後以vm作為新考慮的中間頂點，對S以外的每個頂點vj，比較dist[m]+GA[i，j]與dist[j]的大小，若前者小，表明加入了新的中間頂點後可以得到更好的方案，即可求得更短的路徑，則用它代替dist[j]，同時把vj或邊（vm，vj）並入到path[j]中。重復以上過程n-2次，即可在dist數組中得到從源點到其餘個終點的最短路徑長度，對應的path數組中保存著相應的最短路徑。
為了實現上的方便，用一個一維數組s[1..n]代替集合s，用來保存已求得最短路徑的終點集合，即如果s[j]=0表示頂點vj不在集合中，反之，s[j]表示頂點vj已在集合中）。

Procere dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j<>I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]<maxint {maxint為假設的一個足夠大的數}
Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k個終點Vm}
if (s[j]=0)and(dist[j]<w) then begin m:=j;w:=dist[j];end;
If m<>I then s[m]:=1 else exit;{若條件成立，則把Vm加入到s中，否則退出循環，因為
剩餘的終點，其最短路徑長度均為maxint，無需再計算下去}
for j:=1 to n do {對s[j]=0的更優元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j]<dist[j])
then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;

用集合的思想：

for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i]<wm) then begin j:=i;wm:=dist[i];end;
s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;