題目描述 Description
已知n個(gè)點(diǎn)(n<=100)，給你n*n的方陣刻撒，a[i,j]表示從第i個(gè)點(diǎn)到第j個(gè)點(diǎn)的直接距離。
現(xiàn)在有Q個(gè)詢問(wèn)耿导，每個(gè)詢問(wèn)兩個(gè)正整數(shù)声怔，a和b，讓你求a到b之間的最短路程舱呻。滿足a[i,j]=a[j,i];
輸入描述 Input Description
第一行一個(gè)正整數(shù)n醋火，接下來(lái)n行每行n個(gè)正整數(shù)，滿足a[i,i]=0,再一行一個(gè)Q箱吕，接下來(lái)Q行芥驳，每行兩個(gè)正整數(shù)a和b。
輸出描述 Output Description
一共Q行茬高，每行一個(gè)整數(shù)兆旬。
樣例輸入 Sample Input
3
0 1 1
1 0 3
1 3 0
1
2 3
樣例輸出 Sample Output
2
1.Floyd算法的簡(jiǎn)介
Floyd算法又稱為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法怎栽，與Dijkstra算法類似丽猬。該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者熏瞄、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名脚祟。
2.Floyd的算法流程
按照題目要求，讀入數(shù)據(jù)到3x3的鄰接矩陣內(nèi)
Y0JP04PDS_WO6}M1P2%EY)H.png
在初始化圖結(jié)構(gòu)時(shí)强饮，需要注意的是由桌，當(dāng)i=j時(shí)，應(yīng)當(dāng)設(shè)置為0邮丰，未特別說(shuō)明的數(shù)據(jù)應(yīng)設(shè)置為正無(wú)窮行您。
接著，進(jìn)入算法核心語(yǔ)句剪廉，先從無(wú)頂點(diǎn)開(kāi)始尋找最短的到達(dá)路徑
也就是0-0的直接路徑娃循。根據(jù)上圖，1-1路徑為0妈经。
當(dāng)前路徑大于計(jì)算的路徑淮野，更新最短路徑
floyd算法核心:對(duì)于每一對(duì)頂點(diǎn) i 和 j捧书，看看是否存在一個(gè)頂點(diǎn) k 使得從 i 到 k 再到 j 比已知的路徑更短吹泡。如果是更新它。
e[i][j] = e[i][k] + e[k][j];
...
當(dāng)經(jīng)過(guò)0-n個(gè)頂點(diǎn)的经瓷，更新i-j的最短路徑爆哑，我們得到如下圖
input.png
最后，根據(jù)題意要求舆吮，直接找到最短路徑位置輸出即可揭朝。
具體實(shí)現(xiàn)代碼如下
#include<iostream>
#include<cstdio>
using namespace std;
int e[1100][1100], k, i, j, n; int a, b;
int inf = 99999999;//用inf(infinity的縮寫)存儲(chǔ)一個(gè)我們認(rèn)為的正無(wú)窮值
int main() {
//n*n的矩陣
scanf("%d", &n);
//初始化
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (i == j) e[i][j] = 0;
else e[i][j] = inf;
//讀入鄰接矩陣信息
for (i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> e[i][j];
}
//Floyd-Warshall算法核心語(yǔ)句 （生成最小路徑圖）
for (k = 0; k < n; k++)//附加頂點(diǎn)（1=n）遍歷队贱，判斷哪個(gè)路徑短
for (i =0; i < n; i++)
for (j = 0; j < n; j++)
if (e[i][j]>e[i][k] + e[k][j])//選擇最小值
e[i][j] = e[i][k] + e[k][j];//更新較小節(jié)點(diǎn)
//輸出最終的結(jié)果
int q;
cin >> q;
int s, t;
for (int i = 1; i <= q; i++) {
cin >> s >> t;//輸入欲查找的最短路徑的位置
printf("%d\n", e[s-1][t-1]);
}
return 0;
}
