哪个网站可以哪些企业做哪些产品,江安县建设招标网站,网站友情链接的好处,杭州手机网站制作介绍
全称Shortest Path Faster Algorithm.
优化思想#xff1a;
1.由int path[maxn]定义的记录最短距离的容器#xff0c;只有在path[i]valuepath[j]时才会更新#xff0c;它们两者的值相等时path的值仍保持不变。由此优化容器#xff0c;选择用一个队列来替path数…介绍
全称Shortest Path Faster Algorithm.
优化思想
1.由int path[maxn]定义的记录最短距离的容器只有在path[i]valuepath[j]时才会更新它们两者的值相等时path的值仍保持不变。由此优化容器选择用一个队列来替path数组辅助记录最短路径。 2.优化BF算法判断负环 如果最短路径未在队列中则加入入队次数累加直至队列为空时结束。其中如果一个顶点的入队次数超过顶点个数V-1,说明在进行V-1趟比较操作后仍存在更小的路径即图中存在从源点可达的负环。
实现
const int maxn100;
const int INF1000000000;
int path[maxn],num[maxn];
bool isin[maxn]{false};//是否在队列中
struct node{int v;int value;
};
vectornode table[maxn];
int n;//顶点个数bool SPFA(int b){fill(path,pathmaxn,INF);memset(num,0,sizeof(num));queueint q;q.push(b);path[b]0;num[b];//记录入队次数isin[b]true;while(!q.empty()){int frontq.front();q.pop();num[front]--;isin[front]false;//边记录边判断:以出队元素为中心展开for(int j0;jtable[front].size();j){int vtable[front][j].v;int valuetable[front][j].value;if(path[front]valuepath[v]){if(!isin[v]){//最优路径不在队列中q.push(v);//入队num[v];isin[v]true;if(num[v]n)//存在负环return false;}}}}}return true;
}
