迪傑斯特拉演算法

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

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

② dijkstra演算法有哪些

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

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

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

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

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

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

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

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

④ 迪傑斯特拉演算法的原理

1.首先，引入一個輔助向量D，它的每個分量 D 表示當前所找到的從起始點 （即源點 ）到其它每個頂點 的長度。
例如，D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這里強調相對就是說在演算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。
2.D的初始狀態為：若從 到 有弧（即從 到 存在連接邊），則D 為弧上的權值（即為從 到 的邊的權值）；否則置D 為∞。
顯然，長度為 D = Min{ D | ∈V } 的路徑就是從 出發到頂點 的長度最短的一條路徑，此路徑為( )。
3.那麼，下一條長度次短的是哪一條呢？也就是找到從源點 到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次於從源點 到頂點 的最短路徑長度。
假設該次短路徑的終點是 ，則可想而知，這條路徑要麼是( )，或者是( )。它的長度或者是從 到 的弧上的權值，或者是D 加上從 到 的弧上的權值。
4.一般情況下，假設S為已求得的從源點 出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為 ）要麼是弧( )，或者是從源點 出發的中間只經過S中的頂點而最後到達頂點 的路徑。
因此，下一條長度次短的的最短路徑長度必是D = Min{ D | ∈V-S }，其中D 要麼是弧( )上的權值，或者是D ( ∈S)和弧( , )上的權值之和。
演算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從 出發的的終點的集合，初始狀態為空集。那麼，從 出發到圖上其餘各頂點 可能達到的長度的初值為D=arcs[Locate Vex(G, )]， ∈V；
2）選擇 ，使得D =Min{ D | ∈V-S } ；
3）修改從 出發的到集合V-S中任一頂點 的最短路徑長度。

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

⑥ 迪傑斯特拉演算法 應用

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineTrue1
#defineFalse0
#definemax99


typedefstructjingdian{												//景點結構體
	charname[16];
	charnum;
}jingdian;

voidjdfz(structjingdianz[])											//景點賦值
{
	intn;

	strcpy(z[0].name,"圖書館");														//名字賦值
	strcpy(z[1].name,"行政樓");
	strcpy(z[2].name,"理學樓");
	strcpy(z[3].name,"電子信息實驗樓");
	strcpy(z[4].name,"理科實驗樓");
	strcpy(z[5].name,"計算機實驗樓");
	strcpy(z[6].name,"工程實驗樓");
	strcpy(z[7].name,"生化實驗樓");
	strcpy(z[8].name,"體育場");
	strcpy(z[9].name,"宿舍區");
	strcpy(z[10].name,"文俊樓");
	strcpy(z[11].name,"文清樓");
	strcpy(z[12].name,"文新樓");
	strcpy(z[13].name,"文逸樓");
	strcpy(z[14].name,"演藝中心");

	for(n=0;n<15;n++){																//代號賦值
		z[n].num=n+1;
	}
}


voidljcx(charlinjie[15][15],jingdianz[])				//景點查詢函數
{
	inta,b;																	//輸入代號用
	intv;
	intl;																		//節點數
	intn,m;																	//循環用
	ints[20];																	//記錄已被確定的最短路徑長度
	intpath[20];																//記錄出發到目的i當前最短路徑上i的前驅節點
	intd[20];																	//記錄當前的最短路徑長度
	intmin;
	inttemp[20]={0};
	intt=0;
	intpre,i;

	printf("輸入出發地,目的地代號,以空格隔開:");
	scanf("%d%d",&a,&b);
	//	printf("%d%d",a,b);														//測試是否獲得ab
	if(a<1||a>15||b<1||b>15)printf("輸入錯誤!");								//判斷輸入是否正確
	elseif(a==b)printf("你已在此處!");


	else{
		l=15;
		for(n=1;n<=l;n++){															//求最短路徑
			s[n]=False;
			d[n]=linjie[a-1][n-1];
			if(d[n]<max)path[n]=a;
			elsepath[n]=-1;
		}		s[a]=1;																	//出發點路徑定義
		d[a]=0;
		path[a]=-1;

		for(n=1;n<l;++n){
			v=-1;
			min=max;
			for(m=1;m<=l;m++){
				if(!s[m]&&d[m]<min){
					v=m;
					min=d[m];
				}
			}
			if(v==-1)break;
			s[v]=True;

			for(m=1;m<=l;m++){
				if(!s[m]&&(d[v]+linjie[v-1][m-1]<d[m])){								//有最短路徑時更新前驅和長度
					d[m]=d[v]+linjie[v-1][m-1];
					path[m]=v;
				}

			}
		}


		printf("
最短路徑：
");
		pre=path[b];

		for(n=1;n<=15;n++)
			printf("%d",path[n]);
		printf("
");

		while(pre!=-1){//路徑倒序存入臨時數組

			temp[t++]=pre;
			pre=path[pre];
		}

		//		printf("11");

		for(i=t-1;i>=0;i--){
			printf("%s—>",z[temp[i]-1].name);//倒序輸出臨時數組
		}
		printf("%s",z[b-1].name);
		printf("

");
	}//else尾
}


voidmain()										//主函數
{
	intn,m;														//循環用n，m
	chara;
	jingdianz[15];

	charlinjie[15][15];

	for(n=0;n<15;n++)													//鄰接表
		for(m=0;m<15;m++){
			linjie[n][m]=max;
			if(n==m+1)linjie[n][m]=linjie[m][n]=1;
		}
	linjie[9][0]=linjie[0][9]=1;
	linjie[11][1]=linjie[1][11]=1;

	for(n=11;n<15;n++){
		linjie[n][10]=linjie[10][n]=1;
	}

	jdfz(z);															//名字代號賦值

	//	for(n=0;n<15;n++){															//名字代號賦值測試
	//		puts(z[n].name);
	//		printf("%d",z[n].num);
	//		printf("
");
	//	}
	//	for(n=0;n<15;n++){															//鄰接表測試
	//		for(m=0;m<15;m++){
	//			printf("%d",linjie[n][m]);
	//		}
	//		printf("
");
	//	}


	printf("校園景點列表及其編號：

");
	printf("1圖書館2行政樓3理學樓4電子信息實驗樓5理科實驗樓
6計算機實驗樓7工程實驗樓8生化實驗樓9體育場10宿舍區
11文俊樓12文清樓	13文新樓	14文逸樓	15演藝中心
");
	printf("===========================================================================");
	printf("
選擇功能：
1.景點介紹2.路線查詢3.退出系統

選擇編號：");
	a=getchar();

	//		putchar(a);																//測試是否獲得字元


	if(a=='1'){														//景點介紹

	}

	elseif(a=='2'){												//路徑查詢
		ljcx(linjie,z);
	}

	elseif(a=='3'){												//退出
		exit(0);
		//			printf("這個沒顯示就是結束了");										//是否結束了
	}

	elseprintf("輸入代號錯誤，請重新輸入:
");						//代號錯誤
}

⑦ 迪傑斯特拉演算法

按路徑長度遞增次序產生最短路徑演算法：
把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的路徑權值之和 （反證法可證） 求最短路徑步驟 … 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值 ƒ 若存在<V0,Vi>，為<V0,Vi>弧上的權值 ƒ 若不存在<V0,Vi>，為∝ … 從T中選取一個其距離值為最小的頂點W，加入S … 對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的 距離值比不加W的路徑要短，則修改此距離值 … 重復上述步驟，直到S中包含所有頂點，即S=V為止

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

· 演算法思想
設給定源點為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演算法是典型的演算法。Dijkstra演算法是很有代表性的演算法。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。

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