BFS是借助于隊(duì)列來存儲(chǔ)，模擬的是數(shù)的按層遍歷

來源：周春樵

BFS來求最短路時(shí)間復(fù)雜度是$O(n!)$
下面代碼注釋詳細(xì)。
代碼

#include<iostream> #include<queue> //bfs使用 #include<vector> #include<cstring>using namespace std;typedef long long ll; const int maxn=20; int n;//城市的個(gè)數(shù) ll dis[20];//表示1號(hào)城市到各個(gè)城市的最短距離 int pre[maxn];//表示一個(gè)城市的父節(jié)點(diǎn) vector<pair<int,int> > v[maxn];//記錄 i到j(luò)的距離，第一個(gè)元素表示城市，第二個(gè)元素表示距離 queue<pair<int ,int> > q;//q[i]表示1號(hào)城市到i城市的距離 vector<int> p;//保存城市N到城市1的最短路的路徑，這里是反向的 void bfs(){q.push(make_pair(1,0));while(!q.empty()){int x=q.front().first;//取隊(duì)首元素，這里取城市編號(hào) q.pop();//出隊(duì)for(int i=0;i<v[x].size();i++){//遍歷任何和x城市相連的城市int dx=v[x][i].first;//和城市x相連的城市編號(hào)int dlen=v[x][i].second;//和 城市x相連城市的距離if(dis[dx]>dis[x]+dlen){dis[dx]=dis[x]+dlen;//到新城市dx的距離，最小值更新 q.push(make_pair(dx,dlen));//城市1到城市dx的距離dlen ，一起入隊(duì) pre[dx]=x;//} } } } //獲取逆向路徑 void get_path(){for(int i=n;i!=-1;i=pre[i])p.push_back(i); }int main(){cin>>n;memset(dis,0x3f,sizeof(dis));//初始化1到任何城市的距離都為無窮大 memset(pre,-1,sizeof(pre));//初始1到所有城市都不聯(lián)通 //輸入城市的距離int len;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>len;v[i].push_back(make_pair(j,len));//第i城市到j(luò)城市的距離len } dis[1]=0;//初始化，從1到1號(hào)城市距離為0bfs(); cout<<dis[n]<<endl;vector<int>::reverse_iterator it;//逆向迭代器 for(it=p.rbegin();it!=p.rend();it++)cout<<(*it)<<" "; //反向輸出路徑 return 0; } /*測試數(shù)據(jù) 6 0 16 1 1000 12 15 16 0 1000 2 1000 8 1 1000 0 1000 5 1000 1000 2 1000 0 9 3 12 1000 5 9 0 8 15 8 1000 3 8 0 */

總結(jié)

以上是生活随笔為你收集整理的BFS最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。