迪傑斯特拉演算法演示

⑴ 實現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;
}
}
}

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

⑶ 迪傑斯特拉演算法的介紹

迪傑斯特拉演算法是由荷蘭計算機科學家狄克斯特拉於1959 年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有向圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

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

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

⑸ 迪傑斯特拉演算法

按路徑長度遞增次序產生最短路徑演算法： 把V分成兩組： （8）S：已求出最短路徑的頂點的集合 （8）V-S=T：尚未確定最短路徑的頂點集合 將T中頂點按最短路徑遞增的次序加入到S中， 保證

⑹ 迪傑斯特拉演算法的演算法實現

· 演算法思想
設給定源點為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演算法有哪些

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

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

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

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

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

(7)迪傑斯特拉演算法演示擴展閱讀：

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

⑻ Dijkstra 演算法是什麼

是求單源最短路演算法,圖中有一個起始點,求所有點對於這個起始點的最短距離
在路由器的協議裡面有它的應用

還有問題可以繼續hi我

⑼ 迪傑斯特拉演算法怎麼算

Dijkstra演算法是一種求單源最短路的演算法，即從一個點開始到所有其他點的最短路。其基本原理是：每次新擴展一個距離最短的點，更新與其相鄰的點的距離。當所有邊權都為正時，由於不會存在一個距離更短的沒擴展過的點，所以這個點的距離永遠不會再被改變，因而保證了演算法的正確性。不過根據這個原理，用Dijkstra求最短路的圖不能有負權邊，因為擴展到負權邊的時候會產生更短的距離，有可能就破壞了已經更新的點距離不會改變的性質。.

⑽ 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——