什么是最短路徑問題

1.?最短路徑概述
最短路徑問題是圖論研究中的一個(gè)經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。 算法具體的形式包括： 確定起點(diǎn)的最短路徑問題 - 即已知起始結(jié)點(diǎn)，求最短路徑的問題。 確定終點(diǎn)的最短路徑問題 - 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。 確定起點(diǎn)終點(diǎn)的最短路徑問題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 全局最短路徑問題 - 求圖中所有的最短路徑。（摘自百度百科）。
2. 解決方法
用于解決最短路徑問題的算法被稱做“最短路徑算法”， 有時(shí)被簡稱作“路徑算法”。 最常用的路徑算法有： Dijkstra算法 A*算法 SPFA算法 Bellman-Ford算法 Floyd-Warshall算法 Johnson算法 所謂單源最短路徑問題是指：已知圖G=（V，E），我們希望找出從某給定的源結(jié)點(diǎn)S∈V到V中的每個(gè)結(jié)點(diǎn)的最短路徑。 首先，我們可以發(fā)現(xiàn)有這樣一個(gè)事實(shí)：如果P是G中從vs到vj的最短路，vi是P中的一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。
3.博客鏈接

??? 1.?幾種算法比較

??? 2.?單元最短路徑（Dijkstra算法）

4.農(nóng)大ACM1030代碼：????? 點(diǎn)擊我鏈接 用鄰接矩陣存儲圖信息，可求出源點(diǎn)到任意節(jié)點(diǎn)的最短距離。

#includeusing?namespace?std;
int?main()
{	//ifstream?cin("1030.in");
	int?infinity=1000,j,i,n,k,t,**w,*s,*p,*d;
	//cout<<"input?the?value?of?n:";
	cin?>>?n;
	//cout<<endl;

	d=new?int[n];???????
	s=new?int[n];
	p=new?int[n];
	w=new?int*[n];
	for(i=0;i<n;i++)?{w[i]=new?int[n];}?
	//輸入各路徑的權(quán)值。。
	for(i=0;i<n;i++)
		for(j=0;j>w[i][j];

	for(s[0]=1,i=1;i<n;i++)
	{
		s[i]=0;d[i]=w[0][i];
		if(d[i]<infinity)?p[i]=0;
		else?p[i]=-1;
	}

	for(i=1;i<n;i++)
	{
		t=infinity;
		k=1;
		//從還沒進(jìn)行過松弛操作的點(diǎn)中選出到源點(diǎn)距離最小的點(diǎn)k。。
		for(j=1;j<n;j++)
			if((!s[j])&&(d[j]<t)){t=d[j];k=j;}
		s[k]=1;//point?k?join?the?S
		//進(jìn)行松弛操作。。就是看能否通過k獲得源點(diǎn)0到點(diǎn)j的更短的路徑。。p[j]記錄的是從0到j(luò)的最短路徑中j的上一個(gè)點(diǎn)。。
		for?(j=1;jd[k]+w[k][j]))?{d[j]=d[k]+w[k][j];p[j]=k;}
	}
	//cout<<"從源點(diǎn)到其它頂點(diǎn)的最短距離依次如下：";?
	cout?<<?d[n-1]?<<?endl;

	return?0;
}