只是想记录一下这三个最短路算法的模板。
Floyd：
//邻接矩阵mp[N][N]; //把各个点之间的最短路全算出来了。 //时间复杂度：O（n^3） void floyd() { for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { if(mp[i][k]!=inf) for(int j=1; j<=n; j++) { if(mp[i][k]+mp[k][j]<mp[i][j]) { mp[i][j]=mp[i][k]+mp[k][j]; } } } } }
Dijkstra：
//邻接矩阵mp[N][N] //单源最短路 //时间复杂度：O（n^2) void dijkstra(int b,int e) { for(int i=0;i<n;i++) { dis[i]=mp[b][i]; } dis[b]=0; flag[b]=1; for(int i=1;i<=m;i++) { int min=MAX; int k; for(int j=0;j<n;j++) { if(!flag[j]&&min>dis[j]) { min=dis[j]; k=j; } } if(min==MAX) break; flag[k]=1; for(int j=0;j<n;j++) { if(!flag[j]&&dis[j]>dis[k]+mp[k][j]) { dis[j]=dis[k]+mp[k][j]; } } } }SPFA:
//邻接矩阵mp[N][N] 邻接表直接看题吧 //单源最短路 //时间复杂度：O(kE) E为边数，k为所有顶点进队的平均次数 void spfa(int s) { queue<int> q; while(!q.empty()) { q.pop(); } memset(vis,0,sizeof vis); for(int i=0;i<n;i++) { dis[i]=inf; } q.push(s); dis[s]=0;vis[s]=1; while(!q.empty()) { int now=q.front(); q.pop();vis[now]=0; for(int i=0;i<n;i++) { if(dis[i]>mp[now][i]+dis[now]) { dis[i]=mp[now][i]+dis[now]; if(!vis[i]) { q.push(i); vis[i]=1; } } } } } 还未学习Dijkstra SPFA的各种优化。
