最短路徑高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第1頁!最短路問題的類型1.單目標最短路徑問題：找出從每一頂點v到某指定頂點u的一條最短路徑。把圖中的每條邊反向，我們就可以把這一問題轉化為單源最短路徑問題。2.單對頂點間的最短路徑問題：對于某給定頂點u和v，找出從u到v的一條最短路徑。如果我們解決了源頂點為u的單源問題，則這一問題也就獲得了解決。一般來講，目前還未發現比最好的單源算法更快的方法。3.每對頂點間的最短路徑問題：對于每對頂點u和v，找出從u到v的最短路徑。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第2頁!計算最短路的常用算法floyd算法：在邊權非負的有向圖中計算每對頂點間的最短路徑問題。該算法在圖的傳遞閉包的基礎上形成；Dijkstra算法：在邊權非負的有向圖中計算單源最短路徑問題。該算法建立在松弛技術基礎之上；Bellman-Ford算法：能在更一般的情況下解決單源點最短路徑問題。所謂一般情況，指的是有向圖的邊權可以為負,但不允許存在負權回路。該算法亦是建立在松弛技術基礎之上的；SPFA算法：是一種很高效的求圖的最短路徑的算法，正負權都可以，還能夠判斷負權回路問題。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第3頁!初始時v0進入組，v0的距離值為0；第二組包含其它所有結點，這些結點對應的距離值為v0到它的值即map[v0][vi]然后每次從第二組的結點中選一個其距離值為最小的結點vm加到組中。每往組加入一個結點vm，就要對第二組的各結點的距離值作一次修正（設vi為第二組的結點,（vm，vi）為圖中的邊）：若加進vm做中間結點使得v0至vi的路徑長度更短（即vi的距離值>vm的距離值+Wmi），則要修改vi的距離（vi的距離值←vm的距離值+Wmi）。修改后再選距離值最小的一個結點加入到組中，…。如此進行下去，直至組囊括圖的所有結點或再無可加入組的結點存在。顯然，這種從第二組的結點中選距離值最小的結點擴展是一種貪心策略。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第4頁!Dijkstra算法框架數據定義說明：

constintmaxint=0xfffffff;intmap[][];//存儲圖intdist[];//存儲到源點的最短路徑長度intpath[];//存儲到源點的最短路徑走法boolvs[];//標記該頂點是否已經計算①從文件中讀入圖的鄰接矩陣g；for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>map[i][j];//讀入數據②邊集數組初始化；for(i=1;i<=n;i++)for(j=1;j<=n;j++)if（map[i][j]==0)map[i][j]=maxint;//把沒有通路的點(map[i][j]==0)間的路徑置為最大值cin>>v;//讀入源點(可默認源點為1)高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第5頁!典型例題—最短路徑問題1249

Description:平面上有n個點（n＜＝100），每個點的坐標均在-10000到10000之間．其中的一些點之間有連線．若有連線，則表示可從一個點到達另一個點，即兩點間有通路，通路的距離為兩點間的直線距離．現在的任務是找出從一點到另一點之間的最短路徑．Input：共n+m+3行行為整數n．第２行到第n＋行，每行兩個整數x和y，描述了一個點的坐標（以一個空格分開）第n＋２行為一個整數m，表示圖中連線的個數．以后的m行，每行描述一條連線，由兩個整數i和j組成，表示第i個點和第j個點之間有連線．最后一行；兩個整數s和t，分別表示源點和目標點．Output:僅一行，一個實數（保留兩位小數），表示從s到t的最短路徑長度高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第6頁!典型例題—最短路徑問題1249

intmain(){inti,j,m,num1,num2;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)map[i][j]=maxint;for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);cin>>m;for(i=1;i<=m;i++){scanf("%d%d",&num1,&num2);map[num1][num2]=map[num2][num1]=dist(num1,num2);}cin>>st>>ed;dijkstra(st);return0;}高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第7頁!典型例題—最小花費1999

【問題描述】:在n個人中，某些人的銀行賬號之間可以互相轉賬。這些人之間轉賬的手續費各不相同。給定這些人之間轉賬時需要從轉賬金額里扣除百分之幾的手續費，請問A最少需要多少錢使得轉賬后B收到100元。【輸入數據】:行輸入兩個正整數n,m，分別表示總人數和可以互相轉賬的人的對數。以下m行每行輸入三個正整數x,y,z，表示標號為x的人和標號為y的人之間互相轉賬需要扣除z%的手續費(z<100)。最后一行輸入兩個正整數A,B。數據保證A與B之間可以直接或間接地轉賬。【輸出數據】:輸出A使得B到賬100元最少需要的總費用。精確到小數點后8位。【輸入樣例】:3312123213313【輸出樣例】:103.07153164【數據規模】:1<=n<=2000高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第8頁!Floyd算法的基本思路是：從圖的帶權鄰接矩陣A=[a(i,j)]n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節點矩陣path來記錄兩點間的最短路徑。遞推公式為：D(0)=A；D(1)=[dij(1)]n×n，其中dij(1)=min{dij(0),di1(0)+d1j(0)}；D(2)=[dij(2)]n×n，其中dij(2)=min{dij(1),di2(1)+d2j(1)}；……D(n)=[dij(n)]n×n,其中dij(n)=min{dij(n-1),di,n-1(n-1)+dn-1,j(n-1)};采用循環迭代可以簡便求出上述矩陣序列，具體算法如下：D(i,j):dij(k)；Path(i,j)：對應于d(i,j)(k)的路徑上i的后繼點,最終的取值為i到j的最短路徑上i的后繼點。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第9頁!數據定義說明：map[][];//存儲圖dist[][];//dis[i,j]=k,i和j之間最短路徑長度為K下面給出Floyed算法算法框架:①從文件中讀入圖的鄰接矩陣map；for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>map[i][j]);//讀入數據②數組初始化；for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(map[i][j]==0)map[i][j]=maxint;//把沒有通路的點(map[I,j]=0)間的路徑置為最大maxintFloy算法—框架結構一種算法高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第10頁!Description：農民John的農場里有很多牧區。有的路徑連接一些特定的牧區。一片所有連通的牧區稱為一個牧場。但是就目前而言，你能看到至少有兩個牧區不連通。現在，John想在農場里添加一條路徑(注意，恰好一條)。對這條路徑有這樣的限制：一個牧場的直徑就是牧場中最遠的兩個牧區的距離(本題中所提到的所有距離指的都是最短的距離)。考慮如下的兩個牧場，圖１是有5個牧區的牧場，牧區用“*”表示，路徑用直線表示。每一個牧區都有自己的坐標：圖１所示的牧場的直徑大約是12.07106,最遠的兩個牧區是A和E，它們之間的最短路徑是A-B-E。

這兩個牧場都在John的農場上。John將會在兩個牧場中各選一個牧區，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。注意，如果兩條路徑中途相交，我們不認為它們是連通的。只有兩條路徑在同一個牧區相交，我們才認為它們是連通的。

現在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，這個更大的新牧場有最小的直徑。

例題選講—牛的旅行2092

高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第11頁!

cin>>n;for(i=1;i<=n;i++)cin>>x[i]>>y[i];for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>c;if(c=='1')f[i][j]=dist(i,j);elsef[i][j]=maxint;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][k]<maxint-1&&f[k][j]<maxint-1&&f[i][j]>f[i][k]+f[k][j])f[i][j]=f[i][k]+f[k][j];memset(m,0,sizeof(m));for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]<maxint-1&&m[i]<f[i][j])m[i]=f[i][j];minx=1e20;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j&&f[i][j]>maxint-1){temp=dist(i,j);if(minx>m[i]+m[j]+temp)minx=m[i]+m[j]+temp;}r=0;for(i=1;i<=n;i++)if(m[i]>minx)minx=m[i];printf("%.6lf",minx);核心代碼高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第12頁!Bellman-Ford算法—單源最短路實質上是：從源點到每一個頂點的最短路徑最多經歷n-1條邊，都能夠求出最短路徑長度。故該算法就是從經過一條邊，兩條邊…….不斷的迭代下去，若迭代過程中某一步開始不再更新則結束,如果更新了n-1次還在更新，則存在負權回路。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第13頁!核心代碼dotimes++;//記錄邊的個數quit=true;//標記是否有更新for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(dist[i]+cost[i][j]<dist[j]){dist[j]=dist[i]+cost[i][j];//修改quit=false;//有更新結點}while(quit&×>=n);高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第14頁!核心代碼voidbellman_ford(ints){inti,j,k;boolchange;for(i=1;i<=n;i++)dist[i]=a[s][i];dist[s]=0;memset(vis,0,sizeof(vis));k=0;change=false;while(!change||k>n){k++;change=false;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if((dist[i]!=maxx)&&(a[i][j]!=maxx))if(dist[i]+a[i][j]<dist[j]){change=true;dist[j]=dist[i]+a[i][j];vis[j]++;if(vis[j]>50){bj=-1;return;}}}if(k==n+1){bj=-1;return;}}高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第15頁!核心代碼#include<iostream>usingnamespacestd;intd[101],a[201],e[101][101],b[101][101],n,m,i,j;boolc[101];voidspfa(intv){inti,j,cl,op,fa;cl=1;op=1;a[cl]=v;c[v]=true;for(i=1;i<=n;i++)d[i]=10000000;d[v]=0;while(op<=cl){fa=a[op];c[fa]=false;for(i=1;i<=n;i++){if((b[fa][i]!=0)&&(d[i]>d[fa]+b[fa][i])){e[fa][i]++;e[i][fa]++;if(e[i][fa]>=n-1){cout<<"exist"<<endl;return;}d[i]=d[fa]+b[fa][i];if(c[i]==false){cl++;a[cl]=i;c[i]=true;}}}

op++;}}intmain(){cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>b[i][j];spfa(m);for(i=1;i<=n;i++){cout<<d[i]<<"";cout<<endl;}return0;}高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第16頁!典型例題—AIMNETBAR1974

Output輸出文件只有一行，一個整數表示最短時間，如果S,T之間不存在通路則輸出“NoSolution!”(雙引號不輸出,"!"為西文標點)。SampleInput

44

123

2410

135

345

14SampleOutput

10【數據規模】

對于30%的數據保證有1<=N<=1000,1<=M<=1000;

對于全部的數據保證有1<N<=10000,1<=M<=100000。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第17頁!SPFA模塊

voidspfa(intst){inti,open,closed,c,x;for(i=1;i<=n;i++)dist[i]=0xfffffff;vis[st]=true;q[1]=st;open=1;closed=1;dist[st]=0;while(open<=closed){x=q[open];for(i=1;i<=a[x][0];i++)if(dist[a[x][i]]>dist[x]+f[x][i]){dist[a[x][i]]=dist[x]+f[x][i];if(!vis[a[x][i]]){closed++;q[closed]=a[x][i];vis[a[x][i]]=true;}}open++;vis[x]=false;}}高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第18頁!計算單源最短路問題（Dijkstra算法）計算單源最短路的思維方向：每次延長最短路時選擇權最小的邊，并調整最短路外每個結點至出發結點的路長計算單源最短路的步驟：把圖中所有結點分為兩組，每一個結點對應一個距離值：組：包括已確定最短路徑的結點，結點對應的距離值是由v0到此結點的最短路徑長度；第二組：包括尚未確定最短路徑的結點，結點對應的距離值 是v0經由組結點（中間結點）至此結點的最短路徑長度；我們按最短路徑長度遞增的順序把第二組的結點加到組中去，直至v0可達的所有結點都包含于組。在這個過程中，總保持從v0到組各結點的最短路徑長度都不大于從v0至第二組任何結點的路徑長度。高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第19頁!3Dijkstra算法中心——++選擇標記擴展高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第20頁!Dijkstra算法框架③求出Dijkstra；voiddijkstra(){inti,j,k,w;for(i=1;i<=n;i++)//初始化,置初值{dist[i]=map[v][i];path[i]=v;vs[i]=false;}dist[v]=0;//處理源點path[v]=0;vs[v]=true;//標記訪問for(i=1;i<=n-1;i++)//Dijkstra算法核心{w=maxint;for(j=1;j<=n;j++)if(!vs[j]&&dist[j]<w)//找到最小點,注意判斷條件{k=j;w=dist[j];}//保存當前最短點vs[k]=true;//將最短點做標記for(j=1;j<=n;j++)//利用找到的點優化還沒有訪問的點if(!vs[j]&&(map[k][j]!=maxint)&&dist[k]+map[k][j]<dist[j]){dist[j]:=dist[k]+map[k,j];//修正最短路徑path[j]:=k;//保存路徑}}}④輸出；選擇標記擴展高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第21頁!典型例題—最短路徑問題1249

SampleInput500202202315121314253515SampleOutput:3.41高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第22頁!典型例題—最短路徑問題1249

voiddijkstra(intv){doublemin;inti,j,k;for(i=1;i<=n;i++){dis[i]=map[v][i];vis[i]=false;}dis[st]=0;vis[v]=true;for(i=1;i<=n-1;i++){min=maxint;for(j=1;j<=n;j++)if(!vis[j]&&dis[j]<min){k=j;min=dis[j];}vis[k]=true;for(j=1;j<=n;j++)if(!vis[j]&&(map[k][j]!=maxint)&&dis[j]>dis[k]+map[k][j])dis[j]=dis[k]+map[k][j];}printf("%0.2f",dis[ed]);}高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第23頁!任意一對頂點之間的最短路徑這個問題的解法有兩種：一一種算法：分別以圖中的每個頂點為源點共調用n次Dijkstra算法,這種算法的時間復雜度為O(n3)；另一種算法：Floyed算法,它的思路簡單,但時間復雜度仍然為O(n3),下面介紹Floyed算法。Floy算法—多源最短路一種算法高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第24頁!高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第25頁!③Floyed算法框架；voidfloyd(){inti,j,k;for(i=1;i<=n;i++)//復抄數組for(j=1;j<=n;j++)dist[i][j]=map[i][j];for(k=1;k<=n;k++)//枚舉中間點for(i=1;i<=n;i++)//枚舉起點for(j=1;j<=n;j++)//枚舉終點if((dist[i][k]!=maxint)&&(dist[k][j]!=maxint)&&(dist[i][k]+dist[k][j]<dist[i][j]))dist[i][j]=dist[i][k]+dist[k][j];}Floy算法—框架結構一種算法高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第26頁!【分析】：用Floyd求出任兩點間的最短路，然后求出每個點到所有可達的點的最大距離，記做mdis[i]。（Floyd算法）r1=max(mdis[i])然后枚舉不連通的兩點i,j，把他們連通，則新的直徑是：mdis[i]+mdis[j]+(i,j)間的距離。r2=min(mdis[i]+mdis[j]+dis[i,j])re=max(r1,r2)re就是所求。

例題選講—牛的旅行2092

高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第27頁!適用條件&范圍1.單源最短路徑(從源點s到其它所有頂點v);2.有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖);3.邊權可正可負(如有負權回路輸出錯誤提示);4.差分約束系統;Bellman-Ford算法—單源最短路與dijkstra算法一樣都是求單源最短路徑的算法,不同的是,在Bellman-Ford算法中,路徑的權值可以為負數。設想從我們可以從圖中找到一個環路（即從v出發，經過若干個點之后又回到v）且這個環路中所有路徑的權值之和為負。那么通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程序就會永遠運行下去。而Bellman-Ford算法具有分辨這種負環路的能力。迭代法高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第28頁!圖的最短路徑長度高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第29頁!【模擬試題】Easysssp1666Description輸入數據給出一個有N(2<=N<=1,000)個節點，M(M<=100,000)條邊的帶權有向圖.

要求你寫一個程序,判斷這個有向圖中是否存在負權回路.如果從一個點沿著某條路徑出發,又回到了自己,而且所經過的邊上的權和小于0,就說這條路是一個負權回路.

如果存在負權回路,只輸出一行-1;

如果不存在負權回路,再求出一個點S(1<=S<=N)到每個點的最短路的長度.約定:S到S的距離為0,如果S與這個點不連通,則輸出NoPath.高中信息競賽數據結構—最短路徑共34頁，您現在瀏覽的是第30頁!SPFA算法SPFA，是一種很高效的求圖的最短路徑的算法。用dijkstra的話，途中存在負權環的話就會失效。而bellman-ford的效率又相對較低。spfa的思路是：維護一個隊列，先將給出的源點放入隊首，對其每條邊連接的點進行松弛操作。如果改變后的點沒在隊列里，就將改變后的點加入隊列。然后將上一個點取出隊列，直到隊列為空。判斷負權環時，只要發現某一個點的拓展次數超過總結