安平营销型网站建设费用,网站建设要学哪些软件有哪些,wordpress 表,建筑招标网站一.Dijkstra 算法 dijkstra算法适用于边权为正的情况#xff0c;求单源最短路#xff0c;适用于有向图和无向图 模板伪代码#xff1a; 清除所有点的标号 设d[0]0#xff0c;其余d[i]INF#xff1b; 循环n次{ 在所有未标记的节点中#xff0c;寻找d[i]最小的点x 给x做标记…一.Dijkstra 算法 dijkstra算法适用于边权为正的情况求单源最短路适用于有向图和无向图 模板伪代码 清除所有点的标号 设d[0]0其余d[i]INF 循环n次{ 在所有未标记的节点中寻找d[i]最小的点x 给x做标记 对于从x出发的所有边(x,y)更新d[y]min(d[y],d[x]w[x,y]); } memset(v,0,sizeof(v));
for(int i0;in;i)
d[i](i0?0:INF);
for(int i0;in;i)
{int x,mINF;for(int j0;jn;j)if(!visit[j]d[j]m){md[j];xj;}visit[x]1;for(int j0;jn;j)d[j]min(d[j],d[x]w[x][j]);} 简单说一下dijkstra的优化 1.储存结构上邻接矩阵是很占空间的众所周知所以我们一般采用邻接表或者边表 2.堆优化因为在dijkstra中有循环n次寻找最小dict的过程我们可以维护一个小根堆来实现也就把时间复杂度从n^2降到了n*(lognE)。 优化后的dijkstra自己写的 /*
建图用的邻接表复杂度O(E*logE)
*/struct pnode {int num;int len;pnode() {}pnode(int a, int b) : num(a), len(b) {}//初始化结构体用的把a复制给num把b复制给len bool operator (const pnode tmp) const {return len tmp.len;}
};int dis[N];
bool vis[N];
int n;void dijkstra(int s) {priority_queuepnode q;q.push(pnode(s, 0));pnode u;int v, i, res inf;for(i 0; i n; i) dis[i] inf, vis[i] false;dis[s] 0;while(!q.empty()) {u q.top(); q.pop();if(u.len ! dis[u.num]) continue;/*这是应对优先队列中的重复入队的点只要最新的那个点就可以了*/if(vis[u.num]) continue;vis[u.num] true;for(i head[u.num]; i ! -1; i g[i].next) {v g[i].to;if(dis[v] u.len g[i].val) {dis[v] u.len g[i].val;q.push(pnode(v, dis[v]));}}}
} 二.Bellman-Ford的优化也就是SPFA直接看三吧 三.SPFA模板及SPFA的优化 1.普通SPFA模板队列化的Bellman-Ford算法 int visit[N],dis[N];
bool SPFA(int s)
{queueintq;memset(dis,127,sizeof(dis));memset(visit,false,sizeof(visit)); memset(cnt,0s,sizeof(cnt));dis[s]0;visit[s]true;q.push(s);while(!q.empty()){int kq.front();q.pop();visit[k]false;for(int ihead[k];i;iedge[i].last)/*边表*/{if(dis[k]edge[i].wdis[edge[i].v]){dis[edge[i].v]dis[k]edge[i].w;if(!visit[edge[i].v]){q.push(edge[i].v);visit[edge[i].v]true; if(cnt[edge[i].v]n) /*如果某一个点的入队次数超过了n次说明存在负环返回false*/ return false;}}}}return true;/*安全跑完了不存在环*/
} 2.SPFA的优化 SPFA算法有两个优化策略SLF和LLL——SLFSmall Label First 策略设要加入的节点是j队首元素为i若dist(j)dist(i)则将j插入队首否则插入队尾 LLLLarge Label Last 策略设队首元素为i队列中所有dist值的平均值为x若dist(i)x则将i插入到队尾查找下一元素直到找到某一i使得dist(i)x则将i出队进行松弛操作。 SLF 可使速度提高 15 ~ 20%SLF LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定为了避免最坏情况的出现通常使用效率更加稳定的Dijkstra算法。实际上dijkstra算法heap优化后是一定快于一般SPFA的而且更加稳定。 1)SPFA的SLF优化很简单的只要使用双端队列就可以实现了。 #include algorithm
#include iostream
#include cstring
#include cstdio
#include deque
using namespace std;
const int N501;
const int NN100001;
const int inf0x7fffffff;
int n,nu;
typedef struct node
{int adj,val;struct node *next;
};
node node[NN],*p[N];
int SPFA()
{dequeint qu;int x,i,a,b;int vis[N],dis[N],num[N];struct node *head[N];for(i1;in;i){vis[i]0;num[i]0;dis[i]inf;head[i]p[i];}dis[1]0;vis[1]1;num[1];qu.push_back(1);while(!qu.empty()){xqu.front();qu.pop_front();vis[x]0;head[x]p[x];while(head[x]){ahead[x]-adj;bhead[x]-val;if(dis[a]dis[x]b){dis[a]dis[x]b;if(!vis[a]){vis[a]1;num[a];if(num[a]n)return 1;if(!qu.empty()){if(dis[a]dis[qu.front()])qu.push_back(a);elsequ.push_front(a);}elsequ.push_back(a);}}head[x]head[x]-next;}}return 0;
}
int main()
{int t,i,m,w,a,b,c;scanf(%d,t);while(t--){memset(node,0,sizeof(node));memset(p,0,sizeof(p));nu0;scanf(%d%d%d,n,m,w);for(i0;im;i){scanf(%d%d%d,a,b,c);node[nu].adjb;node[nu].valc;node[nu].nextp[a];p[a]node[nu];nu;node[nu].adja;node[nu].valc;node[nu].nextp[b];p[b]node[nu];nu;}for(i0;iw;i){scanf(%d%d%d,a,b,c);node[nu].adjb;node[nu].val-c;node[nu].nextp[a];p[a]node[nu];nu;}if(SPFA())puts(YES);elseputs(NO);}return 0;
} 网上找的 #includeiostream
using namespace std;
#includedeque
#includecstdio
#includecstring
int n,m;
#define N 1001
struct Edge{int u,v,w,last;
}edge[N];
int head[N];
int dict[N];
bool visit[N];
void input()
{scanf(%d%d,n,m);/*n个点m条边*/for(int i1;im;i){scanf(%d%d%d,edge[i].u,edge[i].v,edge[i].w);edge[i].lasthead[edge[i].u];head[edge[i].u]i;}
}
bool SPFA()
{dequeintq;memset(dict,127,sizeof(dict));memset(visit,false,sizeof(visit));dict[1]0;visit[1]true;;int cnt[N];memset(cnt,0,sizeof(cnt));/*判断有无环的标志*/cnt[1];while(!q.empty()){int kq.front();q.pop_front();visit[k]false;/*取出后不要忘记标志位*/for(int lhead[k];l;ledge[l].last)/*边表*/{int pedge[l].v;if(dict[p]dict[k]edge[l].w){dict[p]dict[k]edge[l].w;cnt[p];if(cnt[p]n) return true;/*如果某个点的入队次数超过了n那么一定存在环*/if(!visit[p]){visit[p]true;if(!q.empty())/*这就是SLF Small Label First 策略.的核心把将要入队的元素的dict与队首元素相比较如果将要入队的元素的dict大的话就放在队尾否则就放在队首 */{if(dict[p]dict[q.front()])/*这样可以保证始终用dict小的更新也节约了时间*/q.push_back(p);else q.push_front(p);/*所以必须使用双端队列*/}else q.push_back(p);/*不要忘记考虑队列为空的情况*/}}}}return false;
}
int main()
{input();if(SPFA())printf(circle);else{for(int i1;in;i)printf(%d ,dict[i]);}return 0;
} 自己打了一遍还可以理解 2.SPFA的LLL优化 在网上实在没找到可靠的。 3.SPFA的DFS优化 在很多的题目中SPFA都是用BFS来实现的对于随机图来说BFS的速度会远大于DFS但是对于某些特殊的图结构来说DFS也是一个很好的选择 例如 1题目中要求在最短的时间内判断有无环DFS明显会比BFS快例题是POj上一个判断单词接龙的题目 2对于网格型的图DFS的速度比BFS快 模板 void SPFA(int k)
{flag[k]true;for(int lhead[k];l;ledge[l].last){int vedge[l].v;/*找出第一个可以被更新的点*/if(dis[v]dis[k]edge[l].w){dis[v]dis[k]edge[l].w;if(!flag[v]){SPFA(v);/*接着深搜下去*/}else /*这表明从某个点开始DFS结果又搜到了这个点说明存在负权回路*/{printf(cycle);return;}}}flag[k]false;/*不要忘记再把k设为false为的是让他能够重复入队*/
} 四Floyd算法模板没有任何优化就是邻接矩阵和n^3一般情况单源最短路是绝对不会用的 for(int k1;kn;k)/*注意这个k必须在最外层循环才行*/for(int i1;ini)for(int j1;jn;j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]); 转载于:https://www.cnblogs.com/c1299401227/p/5401240.html
