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; }