問題描述
在帶有權(quán)值的圖中镶奉，我們需要找到一點(diǎn)到另外一點(diǎn)所經(jīng)過的邊的權(quán)值之和最小，這樣的一條邊就是最短路徑崭放。
基本思想
變量：起始點(diǎn)v0,終點(diǎn)vn,中間點(diǎn)vk
如果dis[v0][vn] > dis[v0][vk] + dis[vk][vn],那么久將vk作為從點(diǎn)v0到vn的轉(zhuǎn)折點(diǎn)哨苛。
分析
Floyd算法的本質(zhì)是二重循環(huán)初始化最短路徑矩陣dis，三重循環(huán)修正dis币砂，時間復(fù)雜度為o(nxnxn)建峭。
上一章說Dijkstra算法智能計算出特定起始點(diǎn)到其他點(diǎn)的最短路徑，時間復(fù)雜度為o(n*n)决摧，要求出所有點(diǎn)之間的最短路徑亿蒸，可以在外面套一個循環(huán)凑兰，這樣時間復(fù)雜度為o(nxnxn)，就和Floyd算法一樣边锁。但是Floyd算法的實(shí)現(xiàn)更為巧妙姑食。
代碼
void MyGraph::shortestPathFloyd() {
int pathMatrix[this->num][this->num];
int shortPath[this->num][this->num];
//初始化矩陣
for (int i = 0; i < this->num; ++i) {
for (int j = 0; j < this->num; ++j) {
shortPath[i][j] = this->array[i * this->num + j];
pathMatrix[i][j] = j;
}
}
//算法主體
for (int k = 0; k < this->num; ++k) {
for (int i = 0; i < this->num; ++i) {
for (int j = 0; j < this->num; ++j) {
if (shortPath[i][k] + shortPath[k][j] < shortPath[i][j]) {
shortPath[i][j] = shortPath[i][k] + shortPath[k][j];
pathMatrix[i][j] = pathMatrix[i][k];
}
}
}
}
//打印i到j(luò)的最短路徑值和路徑
for (int i = 0; i < this->num; ++i) {
for (int j = i + 1; j < this->num; ++j) {
cout << this->node_array[i].data << "-->" << this->node_array[j].data << " value:" << shortPath[i][j];
int key = pathMatrix[i][j];
cout << " path:" << this->node_array[i].data;
while (key != j) {
cout<<"-->"<<this->node_array[key].data;
key = pathMatrix[key][j];
}
cout<<"-->"<<this->node_array[j].data<<endl;
}
}
所用測試圖結(jié)構(gòu)
最短路徑.jpg
輸出結(jié)果
Floyd算法結(jié)果.png
