迪傑斯特拉演算法應用

① 迪傑斯特拉演算法適用大規模嗎

適用。迪傑斯特拉算鉛首法纖激肢(Dijkstra)是由荷蘭計算機科學家狄克斯特拉於1959年提出的，因此又叫狄克斯特拉算毀世法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題。

② dijkstra演算法有哪些

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

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

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

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

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

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

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

③ 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演算法是什麼

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

對於圖G=（V，E），將圖中的頂點分成兩組：第一組S：已求出的最短路徑的終點集合（開始為｛v0}）。第二組V-S：尚未求出最短路徑的終點集合（開始為V-{v0}的全部結點）。

堆優化

思考

該演算法復雜度為n^2,我們可以發現，如果邊數遠小於n^2,對此可以考慮用堆這種數據結構進行優化，取出最短路徑的復雜度降為O(1)；每次調整的復雜度降為O（elogn）；e為該點的邊數，所以復雜度降為O((m+n)logn)。

實現

1、將源點加入堆，並調整堆。

2、選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。

3、處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點

1):若該點在堆里，更新距離，並調整該元素在堆中的位置。

2):若該點不在堆里，加入堆，更新堆。

4、若取到的u為終點，結束演算法；否則重復步驟2、3。

⑤ 關於matlab中的一個Dijkstra演算法應用

這個演算法算起始點到其他點的最短路徑。
function [d,index1,index2]=Dijkf(a)
%兩點間最短距離的Dijkstra演算法
% a表示圖的權值矩陣
% d表示所求最短路的權和
% index1 表示標號頂點的順序
% index2 表示標號頂點索引
% 起始點為第一個點
%參數初始化
M=max(max(a));
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1:length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
%更新l（v），同時記錄頂點順序和頂點索引
while sum(pb)<length(a)
tb=find(pb==0); %第i次循環處理第i+1個頂點
d(tb)=min(d(tb),d(temp)+a(temp,tb)); %更新l（v）
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp]; %記錄標號順序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index; %記錄標號索引
end

下面這個用來求任意兩點間的最短距離，還能算出路線。
function [P,u]=n2shorf(W,k1,k2)
%求任意兩點最短路徑演算法
% P 為兩點k1,k2間的最短路，頂點以經過次序進行排序
% u 為最短路的長度
% 初始化
n=length(W);
U=W;
m=1;
% 利用求最短路的Floyd演算法，求最短路矩陣
while m<=n
for i=1:n
for j=1:n
if U(i,j)>U(i,m)+U(m,j)
U(i,j)=U(i,m)+U(m,j);
end
end
end
m=m+1;
end
u=U(k1,k2);%最短距離
% 求任意給定兩個頂點見的最短路包含的頂點
P1=zeros(1,n);
k=1;
P1(k)=k2;
V=ones(1,n)*inf;
kk=k2;
while kk~=k1
for i=1:n
V(1,i)=U(k1,kk)-W(i,kk);
if V(1,i)==U(k1,i)
P1(k+1)=i;
kk=i;
k=k+1;
end
end
end
k=1;
wrow=find(P1~=0);
for j=length(wrow):(-1):1
P(k)=P1(wrow(j));
k=k+1;
end
end

⑥ 迪傑斯特拉演算法 應用

#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("輸入代號錯誤，請重新輸入:
");						//代號錯誤
}

⑦ Dijkstra演算法

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。注意該演算法要求圖中不存在負權邊。

設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度含侍仿。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。

（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為「起點D到該頂點的距離」（例如，U中頂點A的距離為[D,A]的長度，然後D和A不相鄰，則談棗A的距離為∞）
（2）從U中選出「距離最短的頂點K」，並將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由於上一步談纖中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大於[D,K]+[K,A]的距離）
（4）重復步驟（2）和（3），直到遍歷完所有頂點

https://blog.csdn.net/yalishadaa/article/details/55827681

⑧ 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決核激唯單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標鉛陵記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，改培2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題