当前位置: 首页 > news >正文

用node做的网站上海seo优化服务公司

用node做的网站,上海seo优化服务公司,修改wordpress语言,网站开发程序员目录 先分个类吧: 1.对于有向无环图,我们直接拓扑排序,和AOE网类似,把取max改成min即可。 2.边权全部相等,直接BFS即可 3.单源点最短路 从一个点出发,到达其他顶点的最短路长度。 Dijkstra算法&#x…

目录

先分个类吧:

1.对于有向无环图,我们直接拓扑排序,和AOE网类似,把取max改成min即可。

2.边权全部相等,直接BFS即可

3.单源点最短路

从一个点出发,到达其他顶点的最短路长度。

Dijkstra算法:用于一个节点到所有其他节点的最短路。(要求:不存在负权边,可以用于无向图)


先分个类吧

1.对于有向无环图,我们直接拓扑排序,和AOE网类似,把取max改成min即可

2.边权全部相等,直接BFS即可

3.单源点最短路

从一个点出发,到达其他顶点的最短路长度。

基本操作:松弛:d[u]+w<d[v],于是距离更改。

Dijkstra算法:用于一个节点到所有其他节点的最短路。(要求:不存在负权边,可以用于无向图)

具体过程:

1.开始之前,认为所有点都未计算,dis[]全部赋为极大值。

2.源点的dis[]=0;

3。计算与源点相邻的所有点的dis=map[s][v];

4.在还未算出最短路点的dis中选出最小一个点u,显然,因为不存在负权边,它的最短路就是dis.

5.对于与u相连的所有点v若dis[u]+map[u][v]比当前的dis小就松弛更新。

6.重复上述4,5操作。

正确性证明:

其实就是每一次贪心,显然,从源点开始的第一步得到的最短的路肯定就是最短路(到它的其他路肯定比它长)。

当我们把除源点外第一个确定的加入后,我们再用它去更新一下它连的点。

然后,我们选其中最小的点,它就是确定的。因为,要走到它,要么从那些没有确定最小路的点出发到它(因为这点是最小的点+无负权边,因此这样的点距离肯定更大),要么从已经确定的点上拓展出来,又因为他们不断地更新松弛(每一个确定最小路的点加入后,我们再用它去更新一下它连的点),所以我们可以保证在已经确定地点到最小的点的路径是最优的。因此,我们保证最小的点它就是确定的。

下面放一道模板题:

下面是AC代码(注意,无向边建图edge要2倍):

#include<bits/stdc++.h>
using namespace std;
struct node{int zhi;int dian;int next;
}edge[20010];
int dis[1010],head[1010],cnt,n,m1,s,t,x,y,v;
bool vis[1010];
struct ty{int dian,dis1;bool operator<(const ty &a) const{return dis1>a.dis1;}
};
void merge(int x,int y,int v){edge[++cnt].zhi=v;edge[cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
priority_queue<ty> q;
int dij(int s,int t){q.push({s,0});while(!q.empty()){ty ck=q.top();q.pop();if(vis[ck.dian]==1) continue;vis[ck.dian]=1;for(int i=head[ck.dian];i!=-1;i=edge[i].next){int i1=edge[i].dian;if(vis[i1]==1) continue;if(dis[i1]>dis[ck.dian]+edge[i].zhi){dis[i1]=dis[ck.dian]+edge[i].zhi;q.push({i1,dis[i1]});}}}if(dis[t]>=0x3f3f3f3f) return -1;else return dis[t];
}
int main(){cin>>n>>m1>>s>>t;memset(head,-1,sizeof(head));for(int i=1;i<=m1;i++){scanf("%d%d%d",&x,&y,&v);merge(x,y,v);merge(y,x,v);}memset(dis,0x3f,sizeof(dis));dis[s]=0;cout<<dij(s,t);
}

http://www.fp688.cn/news/157689.html

相关文章:

  • 做网站有哪些百度一下百度搜索
  • 简单网站建设培训中心网络营销策划是什么
  • 做任务佣金的网站论坛推广
  • 手机做炫光图头像的网站百度登陆
  • 东莞网站建设公司电话对网站和网页的认识
  • wordpress开源吗流程优化
  • 网站后台能进前台空白抖音seo关键词优化怎么做
  • 微信存储wordpressseo是什么级别
  • 网站建设按什么收费百度网盟官网
  • 给一个网站做需求分析市场营销专业
  • 外贸网站如何做seoseo行业网
  • 长春网站建设电话营销培训课程
  • 常州男科医院哪一个好河源网站seo
  • 凡科轻站小程序收费吗苹果cms永久免费全能建站程序
  • 一家只做正品的网站新东方雅思培训机构官网
  • 有哪些做外贸免费的网站如何让百度收录自己信息
  • 网站 备案 公安网络搜索引擎优化
  • 软件开发合同模板范本电子商务seo是什么意思
  • 郑州做网站公司排名seo搜狗排名点击
  • 5118网站是免费的吗百度信息流优化
  • 店招搜索栏在那个网站上可以做软文撰写公司
  • 98建筑人才网佛山优化网站关键词
  • 外贸网站设计师怎么给公司做网站推广
  • 制作个人网站教程全国十大跨境电商排名
  • 外贸电商网站制作建立网站的详细步骤
  • 传媒公司 网站开发公关公司提供的服务有哪些
  • 如何判断网站数据库类型外链生成网站
  • 人工智能自动做网站百度竞价课程
  • 做受视频播放网站seo平台
  • 微信分销算b2c网站吗营销推广网