?引入：

如上圖，已知圖G。

問節(jié)點1到節(jié)點3的最短距離。

可心算而出為d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。

求最短路徑算法：

1.Floyd(弗洛伊德)

是一種基于三角形不等式的多源最短路徑算法。邊權可以為負數(shù)

表現(xiàn)為a[i,j]+a[j,k]<a[i,k]。

算法思想：

枚舉“中轉站”(k),“起點”(i),“終點”(j)

設d[i,j]為由i點到j點的最短路徑

則?

初始化d[i,j]為無窮大 （）

算法模板如下：
?

inline int Floyd(int n,int st,int ed)// n個點，起點st,終點ed,返回st到ed的最短距離
{int d[n][n];memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++) d[i][i]=0;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}return d[st][ed];
}

?補充：Floyd輸出最短路徑。

題目：有向圖中任意兩點最短路徑（floyd）

題目描述

　　一個含n個結點的有向圖（注意：是有向圖！！），以矩陣存儲方式給出，請求出指定的多組兩個點之間的最短距離及其最短路徑。

輸入輸出格式

輸入格式：

　　第1行，一個整數(shù)n（0 < n < 300 ），表示有向圖中結點的個數(shù)。
　　第2行到第（n+1）行，是一個n*n的矩陣，表示無向圖中各結點之間的聯(lián)結情況，矩陣中的數(shù)據(jù)為小于1000的正整數(shù)，其中 -1 表示無窮大！！
　　第（n+2）行，一個整數(shù)m，表示接下來有m組頂點 < i , j >對 ，其中，i是起點，j是終點，且i不等于j。
　　接下來有m行，每行兩個整數(shù)，中間一個空格間隔，分別表示i和j，表示求解i點到j點的最短距離及最短路徑。

　　注：輸入數(shù)據(jù)已經(jīng)確保答案每一組頂點間的最短路徑是唯一的，無多解數(shù)據(jù)存在，頂點編號用數(shù)字表示，從1開始編號，至n結束！

輸出格式：

　　共 2m 行。
　　第(m-1)*2+1行，一個整數(shù)，表示第m組頂點的最短距離，若兩點間距離為無窮大，則輸出 -1。
　　第(m-1)*2+2行，用頂點編號表示的路徑序列，各頂點編號間用一個空格間隔，表示第m組頂點的最短路徑，若兩點間距離為無窮大，則輸出的路徑序列為 -1。

輸入輸出樣例

輸入樣例#1：

3
0 4 11
6 0 2
3 -1 0
2
2 1
3 2?

輸出樣例#1：

5
2 3 1
7
3 1 2

代碼如下：
?

#include<bits/stdc++.h>
using namespace std;
int n,q;
int d[10001][10001],pre[10001][10001];
void dg(int i,int j)
{if(i==j||pre[i][j]==0) return;int k=pre[i][j];dg(i,k);dg(k,j);
}
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>d[i][j];if(d[i][j]==-1){d[i][j]=0x7fffff;}}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i][k]+d[k][j]<d[i][j]){d[i][j]=d[i][k]+d[k][j];pre[i][j]=k;}}}}cin>>q;for(int i=1;i<=q;i++){int x,y;cin>>x>>y;cout<<d[x][y]<<endl;cout<<x<<" ";dg(x,y);cout<<y;cout<<endl;}return 0;
}

傳遞閉包（連通性）

d[i,j]表示i與j是否連通。

題目：刻錄光盤

題目描述

　　在FJOI2010夏令營快要結束的時候，很多營員提出來要把整個夏令營期間的資料刻錄成一張光盤給大家，以便大家回去后繼續(xù)學習。組委會覺得這個主意不錯！可是組委會一時沒有足夠的空光盤，沒法保證每個人都能拿到刻錄上資料的光盤，怎么辦呢？！

　　DYJ分析了一下所有營員的地域關系，發(fā)現(xiàn)有些營員是一個城市的，其實他們只需要一張就可以了，因為一個人拿到光盤后，其他人可以帶著U盤之類的東西去拷貝啊！

　　他們愿意某一些人到他那兒拷貝資料，當然也可能不愿意讓另外一些人到他那兒拷貝資料，這與我們FJOI宣揚的團隊合作精神格格不入！！！

　　現(xiàn)在假設總共有N個營員（2<=N<=200），每個營員的編號為1~N。DYJ給每個人發(fā)了一張調(diào)查表，讓每個營員填上自己愿意讓哪些人到他那兒拷貝資料。當然，如果A愿意把資料拷貝給B，而B又愿意把資料拷貝給C，則一旦A獲得了資料，則B，C都會獲得資料。

　　現(xiàn)在，請你編寫一個程序，根據(jù)回收上來的調(diào)查表，幫助DYJ計算出組委會至少要刻錄多少張光盤，才能保證所有營員回去后都能得到夏令營資料？

輸入輸出格式

輸入格式：

先是一個數(shù)N，接下來的N行，分別表示各個營員愿意把自己獲得的資料拷貝給其他哪些營員。即輸入數(shù)據(jù)的第i+1行表示第i個營員愿意把資料拷貝給那些營員的編號，以一個0結束。如果一個營員不愿意拷貝資料給任何人，則相應的行只有1個0，一行中的若干數(shù)之間用一個空格隔開。

輸出格式：

一個正整數(shù)，表示最少要刻錄的光盤數(shù)。

輸入輸出樣例

輸入樣例#1：

5
2 4 3 0
4 5 0
0
0
1 0

輸出樣例#1：

1

代碼：

#include<bits/stdc++.h>
using namespace std;
int f[100001],d[300][300],g[100001],ans;
int main()
{int n;cin>>n;memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++){f[i]=i;}for(int i=1;i<=n;i++){int x;while(1){cin>>x;if(x==0) break;d[i][x]=1;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j&&j!=k&&k!=i){if(d[i][k]==1&&d[k][j]==1){d[i][j]=1;}}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(d[i][j]==1){f[j]=f[i];}}}for(int i=1;i<=n;i++) {if(f[i]==i) {ans++;}}cout<<ans;return 0;
} 

2.dijkstra（狄克斯特拉，迪杰斯特拉）

基于貪心的單源最短路徑算法。邊權必須為正數(shù)

基本思想：

設d[i]為起點s到終點i的最短路徑,a[i,j]為點i到點j邊權。

1.找??,并將其用k記錄

2.

3.?松弛操作，用k來更新圖中所有點。

int dijkstra(int n,int st,int ed)
{int dis[n+1],vis[n+1];memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[st]=0;for(int i=1;i<=n;i++){int k,minn=0x7fffff;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<minn) minn=dis[j],k=j;vis[k]=true;for(int j=1;j<=n;j++) d[j]=min(d[j],d[k]+a[k][j]);}return d[ed];
}

堆優(yōu)化dijkstra:
?

typedef pair<int,int> P;
struct node{int to;int next;int w;
}edge[10000010];
int head[10000010],d[10000010];
int cnt;
int n,m,x,y,z,s;
void add_edge(int u,int v,int w)
{edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
void dijkstra(int s)
{priority_queue< P,vector<P>,greater<P> >q;memset(d,0x3f,sizeof(d));d[s]=0;q.push(P(0,s));while(!q.empty()){P p=q.top();q.pop();int u=p.second;if(d[u]<p.first) continue;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(d[v]>d[u]+edge[i].w){d[v]=d[u]+edge[i].w;q.push(P(d[v],v));}}}
}

3.Bellman-Ford

O(n*m) 但有更優(yōu)的，由其轉換而來的Spfa算法，不再贅述。邊權可以為負數(shù)

4.Spfa

基于bellman-Ford，用隊列優(yōu)化的單源最短路徑算法，邊權可以為負數(shù)，可用于判斷負環(huán)。

代碼如下：

    int head=0,tail=1;team[1]=s,vis[s]=1,dis[s]=0;while(head<tail){head=(head+1)%10000;int u=team[head];vis[u]=0;for(int i=1;i<=len[u];i++){int v=le[u][i];if(dis[v]>dis[u]+a[u][v]){dis[v]=dis[u]+a[u][v];if(vis[v]==0){tail=(tail+1)%10000;team[tail]=v;vis[v]=1;}}}}