對fill用法的介紹

1.用鄰接矩陣實現

const int maxn=100;
const int INF=100000000;//無窮大，用來初始化邊
int G[maxn][maxn];//用鄰接矩陣存儲圖的信息
int isin[maxn]={false};//記錄是否已被訪問
int minDis[maxn];//記錄到頂點的最小距離void Dijkstra(int s,int num){fill(minDis,minDis+num,INF);//先無窮大覆蓋minminDis[s]=0;//令起始結點為0for(int i=0;i<num;i++){//記錄最短距離及其對應下標:先初始化為最小int m=INF,centra=-1;for(int j=0;j<num;j++){//若未被訪問且到頂點的最短距離最小if(isin[j]==false&&minDis[j]<m){//更新最短距離及其下標m=minDis[j];centra=j;}}//找不到最小的頂點了，說明此時剩余結點與頂點連通，無關INF，說明已結束if(centra==-1) return;isin[centra]=true;//開放與centra有關的頂點,并更新其當前到頂點的最小距離for(int k=0;k<num;k++){if(isin[k]==false&&G[centra][k]!=INF&&G[centra][k]+minDis[centra]<minDis[k])minDis[k]=G[centra][k]+minDis[centra];}}
}

記錄最短路徑

添加一個記錄結點的數組即可，將它記錄最短路徑的結點的前一個結點

const int maxn=100;
const int INF=100000000;//無窮大，用來初始化邊
int G[maxn][maxn];//用鄰接矩陣存儲圖的信息
int isin[maxn]={false};//記錄是否已被訪問
int minDis[maxn];//記錄到頂點的最小距離
int pre[maxn];//記錄最短路徑void Dijkstra(int s,int num){fill(minDis,minDis+num,INF);//先無窮大覆蓋minminDis[s]=0;//令起始結點為0for(int i=0;i<num;i++)pre[i]=i;//初始化為自身for(int i=0;i<num;i++){//記錄最短距離及其對應下標:先初始化為最小int m=INF,centra=-1;for(int j=0;j<num;j++){//若未被訪問且到頂點的最短距離最小if(isin[j]==false&&minDis[j]<m){//更新最短距離及其下標m=minDis[j];centra=j;}}//找不到最小的頂點了，說明此時剩余結點與頂點連通，無關INF，說明已結束if(centra==-1) return;isin[centra]=true;//開放與centra有關的頂點,并更新其當前到頂點的最小距離for(int k=0;k<num;k++){if(isin[k]==false&&G[centra][k]!=INF&&G[centra][k]+minDis[centra]<minDis[k]){minDis[k]=G[centra][k]+minDis[centra];//記錄最短距離pre[k]=u;//記錄最短路徑的前驅結點}}
}
void minPath(int begin,int now){//輸出if(now==begin)//回溯到起點{cout<<begin;return;//跳到下一層}minPath(begin,pre[now]);cout<<now;//從起點后不斷往外，輸出結點}

2.用鄰接表實現

#include <vector>
using namespace std;
const int maxn=100;
const int INF=10000000000;
bool isin[maxn]={false};
int path[maxn];
struct node{int id;//結點編號int value;//結點的邊權
}nodes;
vector<node> v[maxn];void Dijisktra(int s,int num){int m,mp;fill(path,path+num,INF);path[s]=0;for(int i=0;i<num;i++){mp=INF;m=-1;for(int j=0;j<num;j++){if(isin[j]==false&&path[j]<mp){m=j;mp=path[j];}}if(m==-1) return;isin[m]=true;//只有這里與鄰接矩陣不同，因為鄰接表存儲結點信息的方式不同 for(int k=0;k<num;k++){//v[m][k]-指的是頂點m中第k+1個與m相連的結點int index=v[m][k].id;if(isin[index]==false&&v[m][k].value+mp<path[index])path[index]=v[m][k].value+mp;}}
}

模擬簡單實現

#include <iostream>
using namespace std;
const int maxn=100;
const int INF=10000000;
bool isin[maxn]={false};
int G[maxn][maxn],num,edge,begins;
int path[maxn];void Dijisktra(int s){fill(path,path+num,INF);path[s]=0;for(int i=0;i<num;i++){int m=-1,n=INF;for(int j=0;j<num;j++){if(isin[j]==false&&path[j]<n){m=j;n=path[j];}}if(m==-1) return;isin[m]=true;for(int k=0;k<num;k++){if(isin[k]==false&&G[m][k]!=INF&&G[m][k]+path[m]<path[k])path[k]=G[m][k]+path[m];}}
}
int main(){int v1,v2,weight;cin>>num>>edge>>begins;fill(G[0],G[0]+maxn*maxn,INF);//初始為無窮for(int i=0;i<edge;i++){cin>>v1>>v2>>weight;G[v1][v2]=weight;}Dijisktra(begins);for(int i=0;i<num;i++)if(i!=num-1)cout<<path[i]<<" ";else cout<<path[i]<<endl;return 0;
}